When there are more variables than observations do shrinkage methods (such as Ridge and Lasso) always find a solution?

Question

Assume we have $n$ observations and $p$ explanatory variables we want to model. To apply ridge regression, we choose a constraint parameter $\lambda \geq 0$ and estimate the coefficients $\beta_i$ which minimise:

\begin{equation} \sum^{n}_{i=1} \left( y_i - \beta_o - \sum_{j=1}^p\beta_jx_{ij} \right) + \lambda \sum_{j=1}^p \beta_j^2 \end{equation}

where $y_i$ are the observations and $x_{ij}$ are the variables.

I am reading an Introduction to Statistical Learning, which says:

When λ = 0, the penalty term has no effect, and ridge regression will produce the least squares estimates

and (of ridge regression):

if p > n, then the least squares estimates do not even have a unique solution, whereas ridge regression can still perform well

My questions are the following:

1. Am I correct in saying that ridge regression (and lasso) fail when $p > n$ and $\lambda = 0$, due to being equivalent to least squares?

2. If so, is there a solution for all $\lambda > 0$ when $p > n$, particularly when $\lambda$ is very close to zero?

3. If there is a solution for all $\lambda > 0$ when $p>n$, is there some reason to be wary of applying shrinkage methods like this due to the closeness of the optimisation problem to least squares?

Answer 1

1. Yes, $p>n, \lambda=0$ case is rank-deficient. Since you already know that OLS for $p>n$ is rank-deficient, then we can see that substituting $\lambda = 0$ in your equation gives the same objective as OLS, and the proof is complete.

2. Yes, ridge regression works for any $\lambda >0$. The immediate demonstration is that the $\lambda I$ is positive definite, so $\lambda I + X^T X$ must be positive definite. You can alternatively show this by applying SVD, and showing that the singular values in the ridge case are all positive. The proof of shrinking coefficients using ridge regression through "spectral decomposition" However, as a matter of doing computation on a computer (not mathematics), choosing $\lambda$ too small may not work because floating point arithmetic is not exact.

3. This is essentially a question of bias-variance-tradeoff. If we choose $\lambda$ too large, then there is too steep a penalty on the coefficients and our predictions may be too far from reality to be useful. If we choose $\lambda$ too small, then the variance of the model may be too high -- estimates will be strongly influenced by our specific data set. In the extreme, excluding or including a single datum could radically change the coefficient estimates.