we define restriction ${{\mathbf w}}_I$ of a vector ${{\mathbf w}}\in R^p$ on $I$; and for convenience, we allow either ${{\mathbf w}}_I \in R^k$ or ${{\mathbf w}}_I \in R^p$ (where components not in $I$ are zeros) depending on the context.

We also need the following quantity in our analysis: $$\pi(k,s)=\sup_{{{\mathbf v}}\in R^{k}, {{\mathbf u}}\in R^s ,I,J}
  \frac{{{\mathbf v}}^\top A_{I,J} {{\mathbf u}}\|{{\mathbf v}}\|_2}{{{\mathbf v}}^\top A_{I,I} {{\mathbf v}}\|{{\mathbf u}}\|_\infty } .$$ The following two lemmas are taken from [@Zhang07-l1]. We skip the proof.

\[lem:gamma-bound\] The following inequality holds: $$\pi(k,s) \leq 
\frac{s^{1/2}}{2} \sqrt{\rho_+(s)/\rho_-(k+s)-1} ,$$

\[lem:inner-prod\] Consider $k,s > 0$ and $G \subset \{1,\ldots,d\}$ such that $|G^c|=k$. Given any ${{\mathbf w}}\in R^p$. Let $J$ be the indices of the $s$ largest components of ${{\mathbf w}}_G$ (in absolute values), and $I= G^c \cup J$. Then $$\max(0,{{\mathbf w}}_I^\top A {{\mathbf w}}) \geq 
\rho_-(k+s) (\|{{\mathbf w}}_I\|_2 - \pi(k+s,s)\|{{\mathbf w}}_G\|_1/s) \|{{\mathbf w}}_I\|_2 .$$

Our analysis requires us to keep track of progress with respect to the least squares solution $\tilde{{{\mathbf w}}}$ with the true feature set $\bar{F}$, which we define below: $$\tilde{{{\mathbf w}}} = \arg\min_{{{\mathbf w}}\in R^p} \|X {{\mathbf w}}- {{\mathbf y}}\|_2^2  \qquad \text{subject to } {{\mathrm{supp}}}({{\mathbf w}}) \subset \bar{F} , \label{eq:ls}$$ where $\bar{F}={{\mathrm{supp}}}(\bar{{{\mathbf w}}})$.

The following lemmas require 