# 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$

For all $k\in\mathbb{N}$, let $x_k,\ y_k\in\mathbb{R}^n$, and assume that $$y_{k+1}=\left(I_n-\frac{ax_kx_k^{\rm T}}{b+\|x_k\|^2}\right)y_k,~~~~~~~~~~~~(1)$$ 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
$$\sum_{k=0}^\infty\frac{ax_k^2}{b+x_k^2}|y_k|<\infty,$$ Thus, it follws from (1) that $$\sum_{k=0}^\infty|y_{k+1}-y_k|=\sum_{k=0}^\infty\frac{ax_k^2}{b+x_k^2}|y_k|<\infty.$$

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

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.

• Thanks, but I do not understand your proof. Is your $x_k$ same as mine? Where does $|x_k|=1$ come from? What are cases (1) and (2)? Do you mean we only need to consider these 2 cases? What do you mean by extreme case? Why $a=0$ is not an extreme case? How does $x_k\in\{e_1,\cdots,e_n\}$ imply finite $L$? – krms May 22 '18 at 15:43
• $a \frac{x_kx_k^T}{b +|x_k|^2} = a \frac{ \frac{x_k}{|x_k|} \frac{x_k^T}{|x_k|} }{b/|x_k|^2 +1}$ so that let $b_k =b/|x_k|^2>0$. – HK Lee May 22 '18 at 15:57
• (1) Note that we diminish $y_i$ in direction $x_k$. If $x_k$ is in canonical basis, i.e., diminishing direction is fixed, then consider Manhattan metric $\|\ \|_1$. The union of line segment $[y_iy_{i+1}]$ is like calculating $\|\ \|_1$. – HK Lee May 22 '18 at 16:02
• (2) Consider the map $v\mapsto (I-\frac{a}{b_k+1} x_kx_k^T)v$. This is not a orthogonal projection into the hyperplane $x_k^\perp$ (but similar) so that I deal the case of orthogonal projection, i.e., $a=1,\ b_k=0$. – HK Lee May 22 '18 at 16:05
• Thanks, and sorry for asking many questions. How does $|Y|\geq|y_{k+1}|$ imply summability? I am not familiar with these geometric concepts but obviously, this can be converted to an algebraic approach. I am still studying your answer but your comments help a lot. – krms May 22 '18 at 16:56