Prove or disprove $\sum_{k=0}^\infty\|y_{k+1}-y_k\|<\infty$ if $y_{k+1}=\big(I_n-\frac{ax_kx_k^{\rm T}}{b+\|x_k\|^2}\big)y_k$

149 Views Asked by At

For all $k\in\mathbb{N}$, let $x_k,\ y_k\in\mathbb{R}^n$, and assume that \begin{equation} y_{k+1}=\left(I_n-\frac{ax_kx_k^{\rm T}}{b+\|x_k\|^2}\right)y_k,~~~~~~~~~~~~(1) \end{equation} where $a\in(0,1)$, and $b>0$. Prove or disprove by counterexample that $$\sum_{k=0}^\infty\|y_{k+1}-y_k\|<\infty.$$


I can show the summablity for the case where $n=1$: Since $a\in(0,1)$, it follows that \begin{align} |y_{k+1}|-|y_k|&=\left|1-\frac{ax_k^2}{b+x_k^2}\right||y_k|-|y_k|\\ &=-\frac{ax_k^2}{b+x_k^2}|y_k|, \end{align} which is nonpositive. Thus, \begin{align} 0\leq \sum_{k=0}^\infty\frac{ax_k^2}{b+x_k^2}|y_k|\leq\sum_{k=0}^\infty\left(|y_{k}|-|y_{k+1}|\right)\leq |y_{0}|-\lim_{k\to\infty}|y_k|\leq |y_{0}|. \end{align} Since, in the above expression, the lower and upper bounds exist, it follows that
\begin{equation} \sum_{k=0}^\infty\frac{ax_k^2}{b+x_k^2}|y_k|<\infty, \end{equation} Thus, it follws from (1) that \begin{equation} \sum_{k=0}^\infty|y_{k+1}-y_k|=\sum_{k=0}^\infty\frac{ax_k^2}{b+x_k^2}|y_k|<\infty. \end{equation}


I do not know how to extend this to the case where $n>1$. Any help is appreciated.

1

There are 1 best solutions below

17
On BEST ANSWER

Here $$ y_{k+1} = \bigg(I - \frac{a}{b_k +1} x_kx_k^T \bigg) y_k$$ where $|x_k|=1,\ b_k>0,\ 0<a<1$. Here $x_kx_k^T$ is a projection.

So clearly $|y_{k+1}|\leq y_k$ and $L:=\sum_k\ |y_k-y_{k-1}|$ is length of piecewise broken curve.

(1) If $x_k \in \{ e_1,\cdots,e_n\}$ where $e_i$ is a canonical basis, then $L\leq \|y_0\|_1$.

(2) Extreme case : Assume that $a=1,\ b_k=0$ :

If $S_k$ is a radius $\frac{|y_k|}{2}$ sphere whose center is $\frac{y_k}{2}$, then $y_{k+1}$ is any point in $S_k$.

If $|y_0|=1$, then assume that $\angle\ (y_i,y_{i+1})=\theta_i$, then $$ |y_{i+1}|=\cos\ \theta_i |y_i| =\prod_{k=0}^i\ \cos\ \theta_k $$ and

$$ |y_i-y_{i+1}| =|y_i|\sin\ \theta_i = \sin\ \theta_i\prod_{k=0}^{i-1}\ \cos\ \theta_k $$

Hence $$ L =\sum_i\ \sin\ \theta_i\prod_{k=0}^{i-1}\ \cos\ \theta_k $$

If $0<C<\theta_i<\frac{\pi}{2}-C$, then $L$ is finite. If $\theta_i\rightarrow 0$, then it depends on $\theta_i$ :

If $\sum_i\ \theta_i <\infty$, then $L$ is finite by the above calculation : $\{y_i\}$ can be viewed as enumeration of points in curve of finite length.

If $\sum_i\ \theta_i=\infty,\ \sum_i\ \theta_i^2<\infty$, then $L$ is infinite : As an example, it has an infinite turn around a fixed circle.

If $ \sum_i\ \theta_i= \sum_i\ \theta_i^2 =\infty$, then $L$ is finite : $y_k$ goes to origin.

If $\theta_i\rightarrow \frac{\pi}{2}$, then $\cos\ \theta_i\rightarrow 0$ so that $L$ is finite.

(3) general case can be covered by (2) :

Proof : Let $Y=(I-x_k' (x_k')^T)X$ and $y_{k+1}= (I-A_k x_kx_k^T)y_k,\ X=y_k ,\ 0<A_k<1$

Note that there is $x_k'$ s.t. $$ |Y-X |=|y_{k+1}-y_k| $$ Hence we have two piecewise broken curves : One is the curve in (2), we denote it as $y_k'$, and another is that of $y_k$.

Here $y_k'$ is plotted by $y_k$. If $y_k'$ is the origin, then in next time, from $y_{k+1}$, we can not plot $y_{k+1}'$. So remaining thing is to show that $|Y|\geq |y_{k+1}|$.

Note that $\Delta oYX $ is a right triangle at $Y$ s.t. $y_{k+1}$ is interior point of the triangle.

If we extend a segment $[Yy_{k+1}]$, then it intersect at $Z\in [oX]$. Since $\Delta XYy_{k+1}$ is isosceles, then $\Delta XYZ$ is acute triangle. Hence we complete the proof.