6 4 1 Linear Versus Non Linear Iterations

1. We just need to check the general formula is compatible with the iteration formula.
Note that

(1)

\begin{align} LHS=\tilde \beta^{t+1}=\sum_{k=0}^{t} (I-2\eta\mathbb{X}^\top\mathbb{X})^k 2\eta \mathbb{X}^\top Y, \end{align}

and

(2)

\begin{align} RHS&=&(I-2\eta\mathbb{X}^\top\mathbb{X})\sum_{k=0}^{t-1}(I-2\eta \mathbb{X}^\top \mathbb{X})^k 2\eta \mathbb{X}^\top Y + 2\eta\mathbb{X}^\top Y\\ &=&\sum_{k=1}^{t}(I-2\eta \mathbb{X}^\top \mathbb{X})^k 2\eta \mathbb{X}^\top Y + 2\eta\mathbb{X}^\top Y. \end{align}

Note that $(I-2\eta\mathbb{X}^\top\mathbb{X})^0 2\eta \mathbb{X}^\top Y=2\eta\mathbb{X}^\top Y$, we can add this extra term to $k=0$.

2. By the previous question, we just need to check if $\sum_{k=0}^{t-1}(I-2\eta\mathbb{X}^\top\mathbb{X})^k 2\eta \mathbb{X}^\top$ equals $L_t$.
It is trivial to check that

(3)

\begin{align} I-2\eta\mathbb{X}^\top\mathbb{X}=\sum_{j=1}^{r}(1-2\eta\sigma_j^2)v_j v_j^\top, \end{align}

by using the fact that the singular vectors are ONB. Then we take power $k$ to both sides:

(4)

\begin{align} \left(I-2\eta\mathbb{X}^\top\mathbb{X} \right)^k &=& \sum_{j_1, j_2, \cdots, j_k=1}^{r} \prod_{i=1}^{k}(1-2\eta\sigma_{j_i}^2)v_{j_i}v_{j_i}^\top\\ &=&\sum_{j=1}^{r}(1-2\eta\sigma_j^2)^k v_j v_j^\top, \end{align}

by using again the fact that $\left<u_i, u_j\right>=1$ if and only if $i=j$

Therefore, using the properties of a geometric sequence, it holds that :

(5)

\begin{align} \sum_{k=0}^{t-1}\sum_{j=1}^{r}(1-2\eta\sigma_j^2)^k v_j v_j^\top=\sum_{j=1}^{r}\sum_{k=0}^{t-1}(1-2\eta\sigma_j^2)^k v_j v_j^\top=\sum_{j=1}^{r}\frac{1-(1-2\eta\sigma_j^2)^t}{2\eta\sigma_j^2}v_j v_j^\top, \end{align}

As a result, we have

(6)

\begin{align} \sum_{k=0}^{t-1}(I-2\eta\mathbb{X}^\top\mathbb{X})^k 2\eta \mathbb{X}^\top=\sum_{j=1}^{r}\frac{1-(1-2\eta\sigma_j^2)^t}{\sigma_j}v_j u_j^\top = L_t. \end{align}

3. Recall the definition of Moore-Penrose inverse that

(7)

\begin{align} \mathbb{X}^\dagger = \sum_{j=1}^{r}\frac{1}{\sigma_j}v_j u_j^\top. \end{align}

By assumption, when $2\eta<\sigma_1^{-2}$, we have

(8)

\begin{align} 2\eta\sigma_j^2<1,\quad\forall j=1,2,\cdots, r. \end{align}

When $t\to\infty$, we have $1-(1-2\eta\sigma_j^2)^t\to 1$. Q.E.D.

4. Conclude that $\tilde \beta_L = H_\lambda (\mathbb{X}^+ Y)$

With the previous step and the fact that $\hat \beta_L = H_\lambda(\tilde \beta^\infty)$,
we have the conclusion.