= \bar{{{\mathbf w}}}^\top {{\mathbf x}}_i$, and $\bar{k}=\|\bar{{{\mathbf w}}}\|_0$. Let $\bar{F}={{\mathrm{supp}}}(\bar{{{\mathbf w}}})$. Choose $\theta$ and $\lambda$ such that $$\lambda \geq 7 \sigma \sqrt{2\rho_+(1) \ln (2p/\eta)/n}$$ and $$\theta > 9 \lambda /\rho_-(1.5\bar{k}+s) .$$ Assume that $$\min_{j \in \bar{F}} |\bar{{{\mathbf w}}}_j| > 2 \theta$$ and $\rho_+(s)/\rho_-(1.5\bar{k}+2s) \leq 1+ 2s/(3\bar{k})$ for some $s \geq 1.5 \bar{k}$, then with probability larger than $1-\eta$: $${{\mathrm{supp}}}(\hat{{{\mathbf w}}}^{(\ell)})={{\mathrm{supp}}}(\bar{{{\mathbf w}}})$$ when $\ell>L$, where $\hat{{{\mathbf w}}}^{(\ell)}$ is the solution of (\[eq:convex-relax-L1\]) and $$L = \left\lfloor \frac{0.5 \ln \bar{k} }{\ln (\rho_-(1.5\bar{k}+s)\theta/(6\lambda))}    \right\rfloor +1 .$$

Theorem \[thm:multi-stage-featsel\] is the main result of this paper. If $$\min_{{{\mathbf w}}_j \in \bar{F}} |{{\mathbf w}}_j| \geq c \sigma\sqrt{\ln p/n}$$ for a sufficiently large constant $c$ that is independent of $\bar{k}$ (but could depend on the RIP condition), then we can pick both parameters $\lambda=O(\sigma \sqrt{\ln p/n})$ and $\theta=O(\sigma \sqrt{\ln p/n})$ at the noise level, so that Theorem \[thm:multi-stage-featsel\] can be applied. In this case, Theorem \[thm:multi-stage-featsel\] implies that multi-stage capped-$L_1$ regularization achieves exact recovery of the support set ${{\mathrm{supp}}}(\bar{{{\mathbf w}}})$. In comparison, Lasso does not achieve exact sparse recovery under RIP conditions. While running Lasso followed by thresholding small coefficients to zero (or using adaptive Lasso of [@Zou06] or the two-stage procedure of [@ZouLi08]) may achieve 