# If p > n, the lasso selects at most n variables

One of the motivations for the elastic net was the following limitation of LASSO:

"In the p > n case, the lasso selects at most n variables before it saturates, because of the nature of the convex optimization problem. This seems to be a limiting feature for a variable selection method. Moreover, the lasso is not well defined unless the bound on the L1-norm of the coefficients is smaller than a certain value." (http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2005.00503.x/full)

I understand that LASSO is a quadratic programming problem but also can be solved via LARS or element-wise gradient descent. But I do not understand where in these algorithms I encounter a problem if p > n where p is the number of predictors and n is the sample size. And why is this problem solved using elastic net where I augment the problem to p+n variables which clearly exceeds p.

-
If lasso restricts use to keeping p<=n why is that a drawback rather than a virtue. overfitting is a serious problem that comes about when p=n. The model with p=n is a saturated model and often that model overfits because it will fit the observed data perfectly but not necessarily predcit future cases well. – Michael Chernick Sep 30 '12 at 12:07
That the lasso selects only up to $n$ variables can be seen as a consequence of the fact that it can be solved using (a slight modification of) the LARS algorithm, which only admits up to $n$ variables into the active set at any one time. That this does not hold in the elastic-net case essentially follows from the incorporation of the $\ell_2$ penalty and so behaves more like ridge regression, the latter of which normally results in all coefficients being nonzero. – cardinal Sep 30 '12 at 13:57
Thank you for the answers, and how would I see for gradient descent that at most n variables can selected: Presentation at cs.cmu.edu/afs/cs/project/link-3/lafferty/www/ml-stat2/talks/… Paper (section 4) at datamining.dongguk.ac.kr/papers/GLASSO_JRSSB_V1.final.pdf – user1137731 Sep 30 '12 at 21:53
@user: I think you may be conflating the mathematical problem with its numerical solution. The LARS algorithm shows that the lasso solution will select at most $n$ variables. This is independent of the actual numerical means for arriving at the solution, i.e., the LARS algorithm gives the insight about the problem, but of course any other method that equivalently solves the problem must have the same property! :-) – cardinal Oct 1 '12 at 0:29

As said, this is not a property of an algorithm but of the optimization problem. The KKT conditions basically give that for coefficient $\beta_j$ to be non-zero it has to correspond to a fixed correlation with the residual $|X_j^t(y-X\beta)| = \lambda$ ($\lambda$ is the regularization parameter).
After resolving the various complications with absolute value etc, you are left with a linear equation for each non-zero coefficient. Since the rank of the matrix $X$ is at most $n$ when $p>n$, this is the number of equations that can be solved, and therefore there are at most n non-zeros (unless there are redundancies).
By the way, this is true for any loss function, not only the standard lasso with $L_2$ loss. So it is in fact a property of the lasso penalty. There are many papers that show this KKT view and the resulting conclusions, I can point to our paper: Rosset and Zhu, Piecewise Linear Regularized Solutions Paths, Annals of Stats 2007 and refs therein.