- 2 {{\mathbf v}}^\top \hat{\epsilon} 
    - \sum_{j=1}^p \lambda_j {{\mathbf v}}_j {{\mathrm{sgn}}}(\hat{{{\mathbf w}}}_j) . \label{eq:dr}$$ Now, let ${{\mathbf v}}=\Delta \hat{{{\mathbf w}}}$ in (\[eq:dr\]), and notice that $\hat{\epsilon}_{\bar{F}}=0$, we obtain $$\begin{aligned}
0 \leq&  2 \Delta \hat{{{\mathbf w}}}^\top A \Delta \hat{{{\mathbf w}}} 
\leq 2 |\Delta \hat{{{\mathbf w}}}^\top \hat{\epsilon} |
- \sum_{j=1}^p \lambda_j \Delta \hat{{{\mathbf w}}}_j {{\mathrm{sgn}}}(\hat{{{\mathbf w}}}_j) \\
\leq& 2 \|\Delta \hat{{{\mathbf w}}}_{\bar{F}^c}\|_1 \|\hat{\epsilon} \|_\infty
- \sum_{j \in \bar{F}} \lambda_j \Delta \hat{{{\mathbf w}}}_j {{\mathrm{sgn}}}(\hat{{{\mathbf w}}}_j) 
- \sum_{j \notin \bar{F}} \lambda_j \Delta \hat{{{\mathbf w}}}_j {{\mathrm{sgn}}}(\hat{{{\mathbf w}}}_j) \\
\leq& 2 \|\Delta \hat{{{\mathbf w}}}_{\bar{F}^c}\|_1 \|\hat{\epsilon} \|_\infty
+ \sum_{j \in \bar{F}} \lambda_j |\Delta \hat{{{\mathbf w}}}_j|
- \sum_{j \notin \bar{F}} \lambda_j |\hat{{{\mathbf w}}}_j| \\
\leq& \sum_{j \in G} (2\|\hat{\epsilon}\|_\infty -\lambda_G) |\hat{{{\mathbf w}}}_j |
+ \sum_{j \notin G\cup \bar{F}} 2 \|\hat{\epsilon}\|_\infty |\hat{{{\mathbf w}}}_j|
+ \sum_{j \in \bar{F}} \lambda_0 |\Delta \hat{{{\mathbf w}}}_j| .\end{aligned}$$ By rearranging the above inequality, we obtain the first desired bound. The second inequality uses $2\|\hat{\epsilon}\|_\infty \leq \lambda_0$.

\[lem:L1-nonsparse3\] Using the notations of Lemma \[lem:L1-nonsparse-dr\], and let $J$ be the indices of the largest $s$ coefficients (in absolute value) of $\hat{{{\mathbf w}}}_G$. Let $I= G^c \cup J$ and $k=|G^c|$. If $0 \leq \lambda_0 /(\lambda_G -2\|\hat{\epsilon}\|_\infty) \leq 3$, then $$\|\Delta \hat{{{\mathbf w}}}\|_2
 \leq (1+ (3 k/s)^{0.5}) \|\Delta \hat{{{\mathbf 