Sparse linear regression 0-norm and 1-norm

Question

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?

Answer 1

1. If features are correlated, you should use elastic net and not lasso.
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.