= Solution
Let $\delta=\widehat\beta-\beta^0$. Comparing the Lasso objective at $\widehat\beta$ and $\beta^0$ gives the <Basic inequality for the Lasso>. On $\mathcal T$ it implies
$$
\frac1n\|X\delta\|_2^2
+2\lambda(\|\beta^0+\delta\|_1-\|\beta^0\|_1)
\leq\lambda\|\delta\|_1.
$$
Since
$$
\|\beta^0+\delta\|_1-\|\beta^0\|_1
\geq\|\delta_N\|_1-\|\delta_S\|_1,
$$
we obtain the <Lasso cone condition>
$$
\|\delta_N\|_1\leq3\|\delta_S\|_1.
$$
The <Karush-Kuhn-Tucker conditions> also give
$$
\widehat\Sigma\delta
=\frac1nX^T\varepsilon-\lambda\widehat z,
$$
so on $\mathcal T$,
$$
\|\widehat\Sigma\delta\|_\infty
\leq\frac\lambda2+\lambda=\frac{3\lambda}{2}.
$$
The assumed cone invertibility condition therefore yields
$$
\|\delta_S\|_\infty\leq\frac{3\lambda}{2\psi}.
$$
If $\min_{j\in S}|\beta_j^0|>3\lambda/(2\psi)$, then every active coefficient remains nonzero and retains its sign. Substituting $\lambda=A\sqrt{\log p/n}$ proves
$$
\operatorname{sgn}(\widehat\beta_S)=\operatorname{sgn}(\beta_S^0)
$$
on an event of the required probability. This is <Lasso sign recovery from cone invertibility>.
Back to article page
