Let $A$ be a real $m \times n$ matrix. The Lasso optimization problem is $$ \text{minimize} \quad \frac12 \| Ax - b \|_2^2 + \lambda \| x \|_1 $$ The optimization variable is $x \in \mathbb R^n$.

The $\ell_1$-norm regularization term encourages $x$ to be sparse, so Lasso is useful for finding a sparse vector $x$ that satisfies $Ax \approx b$. The parameter $\lambda > 0$ controls how sparse the solution to the Lasso problem is.

Question: Suppose I know that I would like for the solution to the Lasso problem to have exactly $p$ nonzero entries. Are there any techniques or tricks or heuristics for choosing a value of $\lambda$ such that the solution to the Lasso problem has exactly (or at least approximately) $p$ nonzero entries?

  • $\begingroup$ I can't think of a one-shot procedure but you can definitely do some sort of homotopy or $\lambda$-path-following method. I've implemented that before, it works pretty well. For instance, once you've solved the problem for a given fixed value of $\lambda$, you can very easily compute the next smaller value of $\lambda$ below which a new variable becomes nonzero. $\endgroup$ – Michael Grant Oct 7 '17 at 1:34
  • $\begingroup$ Or heck, skip the precise breakpoint calculation and combine bisection on $p(\lambda)$ with warm start. $\endgroup$ – Michael Grant Oct 7 '17 at 1:37
  • $\begingroup$ Given that Least Angle Regression provides a very efficient algorithm for computing the entire LASSO path, perhaps you could just use that and extract the information directly from it. e.g. see "Elements of Statistical Learning", Hastie and Tibshirani, Chapter 3 (sec 3.4.4) $\endgroup$ – Glen_b Oct 10 '17 at 0:08

Your Answer

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

Browse other questions tagged or ask your own question.