How to show $x_{k}=\frac{(I-\alpha Q)^{k} x_{0}}{\left\|(I-\alpha Q)^{k} x_{0}\right\|}$ where Q is positive definite, converges to optimal solution

Question

I'm trying to show $\overrightarrow x_{k}=\frac{(I-\alpha Q)^{k} \overrightarrow x_{0}}{\left\|(I-\alpha Q)^{k} \overrightarrow x_{0}\right\|}$ where $\overrightarrow x_{k}$ converges to an optimal solution as k tends to infinity. This is an update equation in Optimization.

Q is positive definite, real nxn, and the eigenvalues are distinct. $ x_{0}$ is also not orthogonal to the eigenvector of Q with smallest eigenvalue

I need to show for $0<\alpha<1 / \lambda_{\max }$ , the fixed step size converges to an optimal solution. $\lambda_{\max }$ max eigenvalue of Q

My attempt is to try and factorize. so $x_{k}=\frac{(I-\alpha V\Sigma V^{T})^{k} \sum ^{n}_{i=1}\mu _{i}\overrightarrow {v_{i}}}{\left\|I-\alpha V\Sigma V^{T})^{k} \sum ^{n}_{i=1}\mu _{i}\overrightarrow {v_{i}}\right\|}$ and take $\lim _{k\rightarrow \infty }$ Where $v_{i}$ is eigenbasis of Q

And then something with the terms to the power of k tending to 0.

Answer 1

This might help: $(I-\alpha Q)=V(I- \alpha D)V^T$

where $V$ is orthogonal and $D$ diagonal and $VDV^T=Q$.

$(I-\alpha Q)^k=V(I- \alpha D)^k V^T$

note that $(I- \alpha D)$ is diagonal, so $(I- \alpha D)^k$ are just the diagonal entries to the power of $k$. Denote $\lambda_i=D_{ii}$ the $i$-th eigenvalue.

For the $i$-th diagonal entry it holds:

$(I- \alpha D)^k_{ii}=(1-\lambda_{min}\alpha)^k \frac{(1-\alpha \lambda_i)^k}{(1-\lambda_{min}\alpha)^k}$

$\frac{(I- \alpha D)^k_{ii}}{(1-\lambda_{min}\alpha)^k}= \frac{(1-\alpha \lambda_i)^k}{(1-\lambda_{min}\alpha)^k}$

In the limit, the right hand side is equal $1$ if $\lambda_i=\lambda_{min}$ and $0$ else.

This implies $\frac{V(I- \alpha D)^kV^T}{(1-\lambda_{min}\alpha)^k}\to v_{min}v_{min}^T$

Now, it is easy to show, that $x_k \to v_{min}$ (the eigenvector to the smalest eigenvalue)

Edit: For the formal proof, use $ x_{k}=\frac{\frac{(I-\alpha Q)^{k} }{(1-\lambda_{min}\alpha)^k} x_{0}}{\left\|\frac{(I-\alpha Q)^{k}}{(1-\lambda_{min}\alpha)^k} x_{0}\right\|}\to \frac{v_{\min}v_{\min}^T x_0}{\left\|v_{\min}v_{\min}^T x_0\right\|}=v_{\min}$

We can take these limits because everything is finite.