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?

  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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.