5 5 7 Ridge And Elastic Net
$\textbf{A) Ridge regression}$
1) For all $\beta$ in $\mathbb{R}^p$,
(1)
\begin{align} D^2{\scr{L_1}}(\beta)=2{\bf X}^T{\bf X}+2\lambda I_p. \end{align}
Since for all $u$ in $\mathbb{R}^p$, $\langle{\bf X}^T{\bf X}u|u\rangle=\langle{\bf X}u|{\bf X}u\rangle=\|{\bf X}u\|^2\geqslant 0$ and since $\lambda>0$, we have that ${\bf X}^T{\bf X}+\lambda I_p$ is a positive definite symmetric matrix.
Furthermore, $\scr{L_1}(\beta)$ tends to $+\infty$ as $\|\beta\|^2$ tends to $+\infty$.
Thus, $\scr{L_1}$ is strictly convex and has a unique minimum.
2) For all $\beta$ in $\mathbb{R}^p$,
(2)
\begin{align} \nabla{\scr{L_1}}(\beta)=-2{\bf X}^T(Y-{\bf X}\beta)+2\lambda\beta. \end{align}
The unique minimum $\hat\beta_\lambda$ of $\scr{L_1}$ fulfills
(3)
\begin{align} -{\bf X}^TY+{\bf X}^T{\bf X}\hat\beta_\lambda+\lambda\hat\beta_\lambda=0 \end{align}
which implies that
(4)
\begin{align} \hat\beta_\lambda=A_\lambda Y \end{align}
where
(5)
\begin{align} A_\lambda=({\bf X}^T{\bf X}+\lambda I_p)^{-1}{\bf X}^T. \end{align}
3) Let $\sum_{k=1}^r{\sigma_ku_k\nu_k^T}$ be a singular value decomposition of ${\bf X}$. We recall that $(u_1,...,u_n)$ and $(\nu_1,...,\nu_p)$ are two orthonormal families of $\mathbb{R}^n$ and $\mathbb{R}^p$, i.e. $u_i^Tu_j=\nu_k^T\nu_l=0$ for $i\neq j$ and $k\neq l$ and $\|u_i\|=\|\nu_j\|=1$.
Hence,
(6)
\begin{align} {\bf X}^T{\bf X}=\left(\sum_{k=1}^r{\sigma_ku_k\nu_k^T}\right)^T\left(\sum_{k=1}^r{\sigma_ku_k\nu_k^T}\right)=\sum_{k=1}^r{\sigma_k^2\nu_ku_k^Tu_k\nu_k^T}=\sum_{k=1}^r{\sigma_k^2\nu_k\nu_k^T}. \end{align}
Thus, we get
(7)
\begin{align} {\bf X}^T{\bf X}+\lambda I_p=\sum_{k=1}^r{(\sigma_k^2+\lambda)\nu_k\nu_k^T} \end{align}
which gives
(8)
\begin{align} ({\bf X}^T{\bf X}+\lambda I_p)^{-1}=\sum_{k=1}^r{\frac{1}{\sigma_k^2+\lambda}\nu_k\nu_k^T}. \end{align}
Therefore,
(9)
\begin{align} A_\lambda=\left(\sum_{k=1}^r{\frac{1}{\sigma_k^2+\lambda}\nu_k\nu_k^T}\right)\left(\sum_{k=1}^r{\sigma_ku_k\nu_k^T}\right)^T=\sum_{k=1}^r{\frac{\sigma_k}{\sigma_k^2+\lambda}\nu_k\nu_k^T\nu_ku_k^T}=\sum_{k=1}^r{\frac{\sigma_k}{\sigma_k^2+\lambda}\nu_ku_k^T}. \end{align}
When $\lambda\rightarrow 0$, $A_\lambda\rightarrow\sum_{k=1}^r{\frac{1}{\sigma_k}\nu_ku_k^T}$ which is by Appendix C.2 the Moore-Penrose pseudo-inverse $({\bf X})^{+}$ of ${\bf X}$.
4) We know that $\hat\beta_\lambda=A_\lambda Y$, so
(10)
\begin{align} {\bf X}\hat\beta_\lambda=\left(\sum_{k=1}^r{\sigma_ku_k\nu_k^T}\right)\left(\sum_{k=1}^r{\frac{\sigma_k}{\sigma_k^2+\lambda}\nu_ku_k^TY}\right)=\sum_{k=1}^r{\frac{\sigma_k^2}{\sigma_k^2+\lambda}u_k^TY\nu_k^T\nu_ku_k} =\sum_{k=1}^r{\frac{\sigma_k^2}{\sigma_k^2+\lambda}\langle u_k|Y\rangle u_k} \end{align}
since $(\nu_1,...,\nu_n)$ is an orthonormal family of $\mathbb{R}^p$.
5) We know that $Y={\bf X}\beta+\varepsilon$ with $\mathbb{E}(\varepsilon)=0$.
Hence,
(11)
\begin{align} \mathbb{E}\left(\hat\beta_\lambda\right)=A_\lambda{\bf X}\beta=\left(\sum_{k=1}^r{\frac{\sigma_k}{\sigma_k^2+\lambda}\nu_ku_k^T}\right)\left(\sum_{k=1}^r{\sigma_ku_k\nu_k^T\beta}\right)=\sum_{k=1}^r{\frac{\sigma_k^2}{\sigma_k^2+\lambda}\langle \nu_k|\beta\rangle\nu_k}. \end{align}
Let us denote by $P=\sum_{k=1}^r{\nu_k\nu_k^T}$ the projection onto the range of ${\bf X}^T$. It follows that
(12)
\begin{align} \left\|\beta-\mathbb{E}\left(\hat\beta_\lambda\right)\right\|^2=\|\beta-P\beta\|^2+\left\|P\beta-\mathbb{E}\left(\hat\beta_\lambda\right)\right\|^2+2\left\langle\beta-P\beta\middle|P\beta-\mathbb{E}\left(\hat\beta_\lambda\right)\right\rangle. \end{align}
We notice that
(13)
\begin{align} \beta-P\beta\in \mathrm{range}\left({\bf X}^T\right)^\perp \end{align}
and
(14)
\begin{align} P\beta-\mathbb{E}\left(\hat\beta_\lambda\right)=P\beta-({\bf X}^T{\bf X}+\lambda I_p)^{-1}{\bf X}^T{\bf X}\beta\in \mathrm{range}\left({\bf X}^T\right), \end{align}
so
(15)
\begin{align} \left\langle\beta-P\beta\middle|P\beta-\mathbb{E}\left(\hat\beta_\lambda\right)\right\rangle=0. \end{align}
Moreover,
(16)
\begin{align} P\beta-\mathbb{E}\left(\hat\beta_\lambda\right)=\sum_{k=1}^r{\nu_k\nu_k^T\beta}-\sum_{k=1}^r{\frac{\sigma_k^2}{\sigma_k^2+\lambda}\langle\nu_k|\beta\rangle\nu_k}=\sum_{k=1}^r{\frac{\lambda}{\sigma_k^2+\lambda}\langle \nu_k|\beta\rangle \nu_k} \end{align}
and $(\nu_1,...,\nu_n)$ is an orthonormal family of $\mathbb{R}^p$, so
(17)
\begin{align} \left\|\beta-\mathbb{E}\left(\hat\beta_\lambda\right)\right\|^2=\|\beta-P\beta\|^2+\left\|\sum_{k=1}^r{\frac{\lambda}{\sigma_k^2+\lambda}\langle \nu_k|\beta\rangle \nu_k}\right\|^2=\|\beta-P\beta\|^2+\sum_{k=1}^r{\left(\frac{\lambda}{\sigma_k^2+\lambda}\right)^2\langle\nu_k|\beta\rangle^2}. \end{align}
6) Since $Y={\bf X}\beta+\varepsilon$ with $\mathrm{Var}(\varepsilon)=\sigma^2 I_n$, it follows that $\mathrm{Var}(Y)=\mathrm{Var}(\varepsilon)=\sigma^2 I_n$.
As a consequence,
(18)
\begin{align} \mathrm{Var}\left(\hat\beta_\lambda\right)=A_\lambda\mathrm{Var}(Y)A_\lambda^T=\sigma^2\mathrm{Tr}(A_\lambda^TA_\lambda). \end{align}
Since
(19)
\begin{align} A_\lambda^TA_\lambda=\left(\sum_{k=1}^r{\frac{\sigma_k}{\sigma_k^2+\lambda}u_k\nu_k^T}\right)\left(\sum_{k=1}^r{\frac{\sigma_k}{\sigma_k^2+\lambda}\nu_ku_k^T}\right)=\sum_{k=1}^r{\left(\frac{\sigma_k}{\sigma_k^2+\lambda}\right)^2u_ku_k^T} \end{align}
with $\mathrm{Tr}(u_ku_k^T)=1$, we get
(20)
\begin{align} \mathrm{Var}\left(\hat\beta_\lambda\right)=\sigma^2\sum_{k=1}^r{\left(\frac{\sigma_k}{\sigma_h^2+\lambda}\right)^2}. \end{align}
7) According to questions 5) and 6), the bias $\mathbb{E}\left(\hat\beta_\lambda\right)-\beta=\sum_{k=1}^r{\frac{\sigma_k^2}{\sigma_k^2+\lambda}\langle \nu_k|\beta\rangle\nu_k}-\beta$ and the variance $\mathrm{Var}\left(\hat\beta_\lambda\right)=\sigma^2\sum_{k=1}^r{\left(\frac{\sigma_k}{\sigma_h^2+\lambda}\right)^2}$ of $\hat\beta_\lambda$ go respectively to $-\beta$ and 0 when $\lambda$ increases.
$\textbf{B) Elastic-Net}$
1) The partial derivate of ${\scr{L_2}}$ with respect to $\beta_j\neq0$ is given by
(21)
\begin{align} \partial_j{\scr{L_2}}(\beta)=-2{\bf X}_j^T\left(Y-\sum_{k=1}^p{\beta_k{\bf X}_k}\right)+2\lambda\beta_j+\mu\mathrm{sign}(\beta_j). \end{align}
By assumption, ${\bf X}_j^T{\bf X}_j=1$, so
(22)
\begin{align} \partial_j{\scr{L_2}}(\beta)=2\left((1+\lambda)\beta_j-R_j+\frac{\mu}{2}\mathrm{sign}(\beta_j)\right) \end{align}
with
(23)
\begin{align} R_j={\bf X}_j^T\left(Y-\sum_{k\neq j}{\beta_k{\bf X}_k}\right). \end{align}
2) Since ${\scr{L_2}}$ is convex, the minimizer of $\beta_j\longmapsto{\scr{L_2}}(\beta_1,...,\beta_j,...,\beta_p)$ is the solution in $\beta_j$ of $\partial_j{\scr{L_2}}(\beta_1,...,\beta_j,...,\beta_p)=0$ when such a solution exists and it is $\beta_j=0$ otherwise.
Let us denote by $\hat\beta_j$ the solution of $\partial_j{\scr{L_2}}(\beta)=0$.
It follows that
(24)
\begin{align} \left ( 1+ \lambda \right )\hat\beta_j=R_j-\frac{\mu}{2}\mathrm{sign}(\hat\beta_j). \end{align}
Let us notice first that if $\left|R_j\right| < \frac{\mu}{2}$, $\left ( 1+ \lambda \right )\hat\beta_j$ and $R_j-\frac{\mu}{2}\mathrm{sign}(\hat\beta_j)$ are of opposite sign whenever $\hat\beta_j \neq 0$, which means that $\hat\beta_j$ must be equal to $0$ in that case.
Then, if $R_j \geqslant \frac{\mu}{2}$,
(25)
\begin{align} \left( 1+\lambda \right )\hat\beta_j \geqslant \frac{\mu}{2} - \frac{\mu}{2}\mathrm{sign}(\hat\beta_j) \geqslant 0 \end{align}
which implies that $\hat\beta_j \geqslant 0$ and
(26)
\begin{align} (1+\lambda)\hat\beta_j=R_j-\frac{\mu}{2}=R_j-\frac{\mu}{2}\mathrm{sign}{(R_j)}. \end{align}
Similarly, when $R_j \leqslant \frac{-\mu}{2}$, we get
(27)
\begin{align} (1+\lambda)\hat\beta_j=R_j+\frac{\mu}{2}=R_j-\frac{\mu}{2}\mathrm{sign}{(R_j)}. \end{align}
Finally, the function $\beta_j\longmapsto{\scr{L_2}}(\beta_1,...,\beta_j,...,\beta_p)$ is minimal in
(28)
\begin{align} \hat\beta_j=\frac{1}{1+\lambda}\left [R_j-\frac{\mu}{2}\mathrm{sign}(R_j) \right ]\mathbb{1}_{|R_j|\geqslant \frac{\mu}{2}}=\frac{R_j}{1+\lambda}\left(1-\frac{\mu}{2|R_j|}\right)_+ \end{align}
where $(x)_+=\mathrm{max}(0,x)$.
3) For the Lasso estimator, we have $\hat\beta_j=R_j\left(1-\frac{\lambda}{2|R_j|}\right)_+$. So the only difference is a rescaling by $1+\lambda$.
