1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – krms May 22 '18 at 15:43
  • 1
    $\begingroup$ $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$. $\endgroup$ – HK Lee May 22 '18 at 15:57
  • 1
    $\begingroup$ (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$. $\endgroup$ – HK Lee May 22 '18 at 16:02
  • 1
    $\begingroup$ (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$. $\endgroup$ – HK Lee May 22 '18 at 16:05
  • 1
    $\begingroup$ 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. $\endgroup$ – krms May 22 '18 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.