# Sparse linear regression 0-norm and 1-norm

We have a response $Y \in \Bbb R^n$ and predictors $X = (x_1, x_2, \cdots, x_m)^T \in \Bbb R^{n \times m}$

The problem we want to solve is

$$\text{argmin}_{k \in \Bbb R^{m}} (\Vert Y - Xk \Vert_2^2 + \lambda \Vert k \Vert_0) \rightarrow k_0$$

However, it is NP-hard, so instead, we solve $$\text{argmin}_{k \in \Bbb R^{m}} (\Vert Y - Xk \Vert_2^2 + \lambda \Vert k \Vert_1) \rightarrow k_1$$

In this paper "Learning physical descriptors for materials science by compressed sensing", it is said that

with highly correlated features, $\lambda \Vert k \Vert_1$ may not be a good approximation for $\lambda \Vert k \Vert_0$

My questions:

Both $\lambda \Vert k \Vert_0$ and $\lambda \Vert k \Vert_1$ put a constraint on the number of non-zero components of vector $k$. But when features are correlated what is the advantage of the $k$ that is found by $\lambda \Vert k \Vert_0$?

Moreover, is there an intuitive example that demonstrates the point that I quoted above?

2. Roughly, if two features are correlated, lasso would choose the feature $$i$$ over $$j$$ if it has the better reward on the loss function, this means a smaller absolute value $$|\beta_i|$$ of the regression coefficient together with a good decrease in the prediction error $$||y-X\beta||_2$$.
3. On the other hand, the $$l_0$$-norm based penalty would choose the feature $$i$$ over $$j$$ if it leads to a good decrease in the prediction error only, since the size of the coefficient doesn't matter, just if it's different from zero (remember, $$||\beta||_0=\#\lbrace\beta_k\neq0\rbrace$$).
4. Now, my intuition would be that $$l_1$$- and $$l_0$$-norm penalties are equally bad at prediction of correct regression coefficients if features are correlated. The proof of Theorem 2 in this paper should illustrate why this is indeed the case. This would be in contradiction to the statement and example of the paper you cited, though.