= Solution
Decompose $h=\Pi_1h+D^\dagger Dh$ using the <incidence pseudoinverse decomposition>. The <Cauchy-Schwarz inequality> controls the constant component, and the duality of the $\ell_\infty$ and $\ell_1$ <norms> controls the remaining component:
$$
\langle z,h\rangle\leq\|\Pi_1z\|_2\|h\|_2+\|(D^\dagger)^\top z\|_\infty\|Dh\|_1.
$$
On the stipulated event, the second term contributes at most $\lambda\|Dh\|_1$ after multiplication by $2/n$. The <triangle inequality> gives $\|Dh\|_1\leq\|D\widehat\theta\|_1+\|D\theta^*\|_1$, so the negative penalty in the <basic inequality for a penalized least-squares estimator> cancels. We obtain
$$
\boxed{\frac{\|h\|_2^2}{n}\leq2\lambda s(\theta^*)+\frac2n\|\Pi_1z\|_2\|h\|_2}
$$
on an event of <probability> at least $1-\delta$.
Back to article page
