5 5 6 Projection On The L1 Ball

$\newcommand\sp{\hspace{1cm}}$
$\newcommand\lsp{\hspace{0.5cm}}$

1

We define $g(\alpha)=\|\beta-\alpha\|^2+2\lambda|\alpha|_1$ for $\alpha\in\mathbb{R}^p$.
$g$ is convex so we can use property (4.2) applied to $S_\lambda(\beta)$.

The subdifferential of the function $g$ is

(1)

\begin{align} \partial g(\alpha)=\lbrace-2(\beta-\alpha)+2\lambda z : z\in\partial|\alpha|_1\rbrace. \end{align}

Let us show that $0\in\partial g(S_\lambda(\beta))$.

If $|\beta_j| > \lambda$, ${[}S_\lambda(\beta){]}_j=\beta_j-sign(\beta_j)\lambda$ and $z_j=sign(\beta_j)$.
Then, ${[}\partial g(S_\lambda(\beta){]}_j=-2(\beta_j-\beta_j+sign(\beta_j)\lambda)+2\lambda sign(\beta_j)=0.$

If $|\beta_j|\le\lambda$, ${[}S_\lambda(\beta){]}_j=0$.
Then, ${[}\partial g(S_\lambda(\beta){]}_j=-2\beta_j+2\lambda z_j$, with $z_j\in{[}-1,1{]}$.
For $z_j=\frac{\beta_j}{\lambda}, {[} \partial g(S_\lambda(\beta)) {]}_j=0$.

Therefore, $0\in\partial g(S_\lambda(\beta))$ and $S_\lambda(\beta)\in\underset{\alpha\in\mathbb{R}^p}{argmin}\lbrace\|\beta-\alpha\|^2+2\lambda|\alpha|_1\rbrace$.

2

Let us denote by $B_{l_1}(R)$ the $l_1$-ball of radius $R$.

$S_\hat \lambda(\beta)\in\underset{\alpha\in\mathbb{R}^p}{argmin}\lbrace g_\hat\lambda(\alpha)\rbrace$
$\Leftrightarrow \sp S_\hat\lambda(\beta)\in\underset{\alpha\in B_{l_1}(R)}{argmin}\lbrace\|\beta-\alpha\|^2 \rbrace$ when $|S_\hat\lambda(\beta)|_1=R$.

3

$|S_\hat \lambda(\beta)|_1=\sum\limits_{\substack{j=1}}^{p}{|\beta_j(1-\frac{\hat\lambda}{|\beta_j|})_+|}=\sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}(1-\frac{\hat\lambda}{|\beta_{(j)}|})|}=\sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}-sign(\hat\beta_{(j)})\hat\lambda|}=\sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}|}-\hat J\hat\lambda$.

4

For the first inequality, we have:
$\sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}|}-\hat J|\beta_{(\hat J)}| < \sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}|}-\hat J\hat\lambda = R$.

For the second inequality, we have:
$R=\sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}|}-\hat J\hat\lambda \le \sum\limits_{\substack{j=1}}^{\hat J+1}{|\beta_{(j)}|}-|\beta_{(\hat J+1)}|-\hat J\hat\lambda \le \sum\limits_{\substack{j=1}}^{\hat J+1}{|\beta_{(j)}|}-(\hat J+1)|\beta_{(\hat J+1)}|$.

5

From question 3 we have that $\hat\lambda=\hat J^{-1}(\sum\limits_{\substack{j=1}}^{\hat J}{|\beta_{(j)}|}-R)$

And from question 4, we then have that $\hat J = max\lbrace J : \sum\limits_{\substack{j=1}}^{J}{|\beta_{(j)}|}-J|\beta_{(J)}| < R\rbrace$.