Bound on steepest descent

81 Views Asked by At

I'm learning about the method of steepest descent for approximating the solution of $Ax=b$ where A is an invertible matrix. Here is the part I understand: We do this by minimizing the function $f(x)=\frac{1}{2}\|Ax-b\|_2^2$. The $\nabla f(x)=A^TAx-A^Tb$. Let $M=A^TA$ and $c=A^Tb$. I came across this bound $$f(x^{(i)}) \leq f(x^{(0)})\left(1-\frac{1}{k(A)^2}\right)^i$$. Where $x^{(i)}$ ist the $i^{th}$ gradient descent step and is defined as follows. $$r^{(i)}=c-Mx^{(i)}\\ \alpha^{(i)}=\frac{(r^{(i)})^T r_n^{(i)}}{(r^{(i)})^T M r^{(i)}}\\ x^{(i+1)}=x^{(i)}+\alpha r^{(i)}$$ and $k(A)$ is the condition number of a matrix.

I was able to derive some other bounds such as $$ \frac{f(x^{(i)})-f(x^{(*)})}{f(x^{(0)})-f(x^{(*)})}<\left(\frac{k(M)-1}{k(M)-1}\right)^{2i} $$ but I can't wrap my head around the one mentioned above. Any pointers or suggestions would be great. Thanks!