one can only find an approximate solution of (\[eq:L0\]). The most popular approximation to $L_0$ regularization is the $L_1$ regularization method which is often referred to as Lasso [@Tib96]: $$\hat{{{\mathbf w}}}_{L_1} = \arg\min_{{{\mathbf w}}\in R^p} \left[ \frac{1}{n} \|X {{\mathbf w}}- {{\mathbf y}}\|_2^2 + \lambda \|{{\mathbf w}}\|_1 \right] ,
\label{eq:L1}$$ where $\lambda>0$ is an appropriately chosen regularization parameter.

The global optimum of (\[eq:L1\]) can be easily computed using standard convex programming techniques. It is known that in practice, $L_1$ regularization often leads to sparse solutions (although often suboptimal). Moreover, its performance has been theoretically analyzed recently. For example, it is known from the compressed sensing literature (e.g., [@CandTao05-rip]) that under certain conditions referred to as [*restricted isometry property*]{} (RIP), the solution of $L_1$ relaxation (\[eq:L1\]) approximates the solution of the $L_0$ regularization problem (\[eq:L0\]). The prediction and parameter performance of this method has been considered in [@BunTsyWeg07; @BiRiTs07; @Koltchinskii08; @ZhangHuang06; @Zhang07-l1; @GeerBuhlmann09-conditions]. Exact support recovery was considered by various authors such as [@MeinBuh06; @ZhaoYu06; @Wainwright06]. It is known that under some more restrictive conditions referred to as [*irrepresentable conditions*]{}, $L_1$ regularization can achieve exact recovery of the support set. However, the $L_1$ regularization method (\[eq:L1\]) does not achieve exact recovery of 