= Solution
The <Lasso> minimizes
$$
\frac1{2n}\|Y-X\beta\|_2^2+\lambda\|\beta\|_1.
$$
Its <Karush-Kuhn-Tucker conditions> are
$$
\frac1nX^T(Y-X\widehat\beta)=\lambda\widehat z,
\qquad
\widehat z_j=
\begin{cases}
\operatorname{sgn}(\widehat\beta_j),&\widehat\beta_j\ne0,\\
\text{an element of }[-1,1],&\widehat\beta_j=0.
\end{cases}
$$
Since the columns of $X$ are centered, $X^T(\epsilon-\bar\epsilon\mathbf1)=X^T\epsilon$. Taking the inner product of the KKT equation with $\beta^0-\widehat\beta$ and using
$$
\widehat z^T\widehat\beta=\|\widehat\beta\|_1,
\qquad
\widehat z^T\beta^0\leq\|\beta^0\|_1
$$
gives
$$
\frac1n\|X(\beta^0-\widehat\beta)\|_2^2
\leq\frac1n|\epsilon^TX(\widehat\beta-\beta^0)|
+\lambda\|\beta^0\|_1-\lambda\|\widehat\beta\|_1.
$$
Put $\delta=\widehat\beta-\beta^0$. On $\Omega$,
$$
\frac1n|\epsilon^TX\delta|
\leq\frac\lambda2\|\delta\|_1.
$$
Using $\beta_N^0=0$ and
$$
\|\beta^0\|_1-\|\widehat\beta\|_1
\leq\|\delta_S\|_1-\|\delta_N\|_1
$$
in the basic inequality yields
$$
\frac1{n\lambda}\|X\delta\|_2^2
+\frac12\|\delta_N\|_1
<\frac32\|\delta_S\|_1.
$$
In particular $\delta$ lies in the <Lasso cone condition>.
The assumed <restricted eigenvalue condition> and $\|\delta_S\|_1\leq\sqrt s\|\delta\|_2$ give
$$
\frac{\|X\delta\|_2^2}{n\lambda}
<\frac32\sqrt s\,\|\delta\|_2
\leq\frac{3\sqrt s}{2\kappa}
\frac{\|X\delta\|_2}{\sqrt n}.
$$
Canceling one prediction-norm factor and applying the restricted eigenvalue condition again gives
$$
\|\widehat\beta-\beta^0\|_2
<\frac{3\lambda\sqrt s}{2\kappa^2}.
$$
Choose
$$
\tau=\frac{3\lambda\sqrt s}{2\kappa^2}.
$$
Every null coordinate satisfies $|\widehat\beta_j|<\tau$. For $j\in S$,
$$
|\widehat\beta_j|
\geq|\beta_j^0|-\|\widehat\beta-\beta^0\|_\infty
>2\tau-\tau=\tau.
$$
Thus $\widehat S^\tau=S$ on $\Omega$.
Back to article page
