Exercise 6.5.3

From problem VI.4.6, we know that orthogonal projection always contracts the original vector, so we have $\parallel x_{k+1}-x^{\text{∗}}\parallel \le \parallel x_k-x^{\text{∗}}\parallel$. We see that $e_k=\parallel x_k-x^{\text{∗}}\parallel$ goes to zero as $k$ increases. The speed of convergence should be close to 1.

This is because $a_i{a}_i^T$ is a rank-1 matrix, it’s symmetric, so we have $a_i{a}_i^T=\mathit{Q\Lambda }{Q}^T$, there’s only 1 singular value, so only 1 eigenvalue, and the other eigenvalues are 0. So the matrix $\frac{a_i{a}_i^T}{a_i^T{a}_i}$ has ${\lambda }_1=1$ and other eigenvalues equal to 0.

We have $I-\frac{a_i{a}_i^T}{a_i^T{a}_i}=Q{Q}^T-\mathit{Q\Lambda }{Q}^T=Q(I-\Lambda )Q^T=Q\left[\begin{array}{cccc}\hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill \dots \hfill & \hfill \dots \hfill \\ \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill \\ \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]Q^T$

According to equation (5), the speed of convergence is related to the conditional number of $A$. Which has just 2 rows, so if the number of columns is much larger than 2, then the matrix has only 2 singular values, it has zero eigenvalues, so the condition number is very large and the speed of convergence is close to 1.