do not make distinctions between RIP and sparse eigenvalue condition. Note that in the traditional low-dimensional statistical analysis, one assumes that $\rho_+(s)/\rho_-(2\bar{k}+2s)< \infty$ as $s \to \infty$, which is significantly stronger than the condition we use here. Although in practice it is often difficult to verify the sparse eigenvalue condition for real problems, the parameter estimation result in (\[eq:multi-stage-param-est-bound\]) nevertheless provides important theoretical insights for multi-stage convex relaxation.

For standard Lasso, we have the following bound $$\|\hat{{{\mathbf w}}}_{L_1}- \bar{{{\mathbf w}}}\|_2 =O(\sqrt{k} \lambda) ,$$ where $\hat{{{\mathbf w}}}_{L_1}$ is the solution of the standard $L_1$ regularization. This bound is tight for Lasso, in the sense that the right hand side cannot be improved except for the constant—this can be easily verified with an orthogonal design matrix. It is known that in order for Lasso to be effective, one has to pick $\lambda$ no smaller than the order $\sigma \sqrt{\ln p/n}$. Therefore, the parameter estimation error of the standard Lasso is of the order $\sigma \sqrt{\bar{k} \ln p/n}$, which cannot be improved.

In comparison, if we consider the capped-$L_1$ regularization with $g(|{{\mathbf w}}_j|)$ defined in (\[eq:capped-L1-reg\]), the bound in (\[eq:multi-stage-param-est-bound\]) can be significantly better when most non-zero coefficients of $\bar{{{\mathbf w}}}$ are relatively 