Write $\delta=\widehat\beta-\beta^0$. On $\Omega$, <Hölder's inequality> gives
$$
\frac1n\delta^TX^T\varepsilon
\leq\lVert\delta\rVert_1\frac{\lVert X^T\varepsilon\rVert_\infty}{n}
\leq\frac\lambda2\lVert\delta\rVert_1.
$$
Since $\beta_N^0=0$, the <triangle inequality> gives
$$
\lVert\beta^0\rVert_1-\lVert\widehat\beta\rVert_1
\leq\lVert\delta_S\rVert_1-\lVert\delta_N\rVert_1.
$$
Substitution in the <Basic inequality for the Lasso>, followed by discarding the nonnegative prediction-error term, yields
$$
\frac\lambda2\lVert\delta_N\rVert_1
\leq\frac{3\lambda}{2}\lVert\delta_S\rVert_1.
$$
Therefore $\lVert\widehat\beta_N-\beta_N^0\rVert_1\leq3\lVert\widehat\beta_S-\beta_S^0\rVert_1$, the <Lasso cone condition>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 205 / 3 / b / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-205/3/b/solution