X_{\bar{F}}^\top ({{\mathbf y}}- {{\mathbf E}}{{\mathbf y}}) .$$ Since $\|e_j^\top (X_{\bar{F}}^\top X_{\bar{F}})^{-1} X_{\bar{F}}^\top\|_2^2= e_j^\top (X_{\bar{F}}^\top X_{\bar{F}})^{-1} e_j
\leq n^{-1} \rho_-(\bar{k})^{-1}$, we have for all $\epsilon>0$: $$P \left[ |\tilde{{{\mathbf w}}}_j-\bar{{{\mathbf w}}}_j| \geq \epsilon \right] \leq 2 \exp [ - n \rho_-(\bar{k})\epsilon^2/(2 n\sigma^2) ] .$$ Taking union bound for $j=1,\ldots,d$ (each with probability $\eta/d$) we obtain the desired inequality.

\[lem:L1-nonsparse-dr\] Consider $G\subset \{1,\ldots,d\}$ such that $\bar{F}\cap G = \emptyset$. Let $\hat{{{\mathbf w}}}=\hat{{{\mathbf w}}}^{(\ell)}$ be the solution of (\[eq:convex-relax-L1\]), and let $\Delta \hat{{{\mathbf w}}}= \hat{{{\mathbf w}}}-\tilde{{{\mathbf w}}}$. Let $\lambda_G = \min_{j \in G} \lambda_j^{(\ell-1)}$ and $\lambda_0 = \max_{j} \lambda_j^{(\ell-1)}$. If $2\|\hat{\epsilon}\|_\infty\| < \lambda_G$, then $$\sum_{j \in G} |\hat{{{\mathbf w}}}_j |
  \leq 
  \frac{2 \|\hat{\epsilon}\|_\infty}{\lambda_G - 2\|\hat{\epsilon}\|_\infty}
  \sum_{j \notin \bar{F}\cup G} |\hat{{{\mathbf w}}}_j|
  +
  \frac{\lambda_0}{\lambda_G - 2\|\hat{\epsilon}\|_\infty}  \sum_{j \in \bar{F}} |\Delta \hat{{{\mathbf w}}}_j|
  \leq   \frac{\lambda_0}{\lambda_G - 2\|\hat{\epsilon}\|_\infty}\|\Delta \hat{{{\mathbf w}}}_{G^c}\|_1
  .$$

For simplicity, let $\lambda_j=\lambda_j^{(\ell-1)}$. The first order equation implies that $$\frac{1}{n} \sum_{i=1}^n 2 ({{\mathbf x}}_i^\top \hat{{{\mathbf w}}} - y_i) {{\mathbf x}}_{i,j}
  + \lambda_j {{\mathrm{sgn}}}(\hat{{{\mathbf w}}}_j) = 0 ,$$ where ${{\mathrm{sgn}}}({{\mathbf w}}_j)=1$ when ${{\mathbf w}}_j>0$, ${{\mathrm{sgn}}}({{\mathbf w}}_j)=-1$ when ${{\mathbf w}}_j<0$, and ${{\mathrm{sgn}}}({{\mathbf w}}_j) \in [-1,1]$ when ${{\mathbf w}}_j=0$. This implies that for all ${{\mathbf v}}\in {{\mathbb R}}^p$, we have $$2 {{\mathbf v}}^\top A \Delta \hat{{{\mathbf w}}} 
    \leq 