Penalizing the Ordinary Least Squares estimation

Question

In a regression analysis, we aim to find the best relationship between two variables (independent variable denoted $y$ and other dependent variable denoted by $x$, and which are related by: $y = f_\beta (X)$) by finding the best estimation or approximation (in terms of mean squares error) of the regression coefficients $\beta$.

Where $y$ is a vector of size $n$, $\beta$ is a vector of size $p$, and $X$ an $n$x$p$ matrix.

1) In fact, when $n>p$, the linear system of equations $y=f_\beta (x)$ is thus overdetermined. And in this case, classical methods such as "Ordinary LEAST Squares (OLS)" estimator can be used in order to estimate the values of unknown parameters $\beta$ in an unbiased manner.

2) But in large dimensional settings, that is, $n < p$, the linear system of equations $y=f_\beta (x)$ is undetermined, and thus there are no enough data (or equations since in this case there will be more unknowns than equations) to estimate the parameters $\beta$. And obviously, the classical estimator "OLS" cannot be used.

A lot of regularization methods have been developed such as the Least Absolute Shrinkage and Smooth Operator (LASSO), Ridge regression, soft thresholding, etc.

Ok all these methods aim to penalize the least squares. For example the ridge adds an $L_2$ penalty, the LASSO adds an $L_1$ penalty, the soft thresholding also adds an $L_1$ penalty, and so on. For example:

LASSO: $argmin_\beta (2^{-1}||Y - f_\beta (X)||^2 + P_{\lambda} (|\beta|))$ where $P_{\lambda} (|\beta|) = \lambda |\beta|_1^1$.

Ridge: $argmin_\beta (2^{-1}||Y - f_\beta (X)||^2 + P_{\lambda} (|\beta|))$ where $P_{\lambda} (|\beta|) = \lambda |\beta|_2^2$.

My questions are:

A) The penalization of the least squares estimation (by lasso, soft, ridge, etc. ) is a solution of the case when $n<p$ ??

If yes, so these techniques can not be used even when $n>p$ ??

B) I know that in contrast to the Ridge, LASSO introduces sparsity. That is why it is very used in compressive sensing! and we can conclude that LASSO is better than the Ordinary Least Squares because it introduces this sparsity which can be very helpful in terms of computational complexity.

So in this case, what is the advantage of using the ridge regression in place of the ordinary Least Squares? In other words, what are the benefits by using the Ridge regression?

C) I noticed that the soft thresholding also penalizes the least squares by an $L_1$ penalty. So can we conclude that soft thresholding and LASSO are the same? If no, so what is the difference between them since the two adds an $L_1$ penalty !!! ?

Kindly, I will appreciate very much your professional answers. And if someone can explain me a lot of supplementary details from his/her experiences in this domain, it will be better.

Answer 1

I don't use ridge regression all that much, so I'll focus on (A) and (C):

(A) While the Lasso is traditionally motivated by the p > n scenario, it is mathematically well-defined when n > p, i.e. the solution exists and is unique assuming your design matrix is sufficiently well-behaved. All the same formulas and error bounds continue to hold when n > p. All the algorithms (at least that I know of) that produce Lasso estimates should also work when n > p.

Most of the time if n > p (especially if p is small) you probably want to think carefully about whether or not the Lasso is your best option. As usual, it is problem dependent. That being said, in some situations the Lasso may be appropriate when n > p: For example, if you have 10,000 predictors and 15,000 observations, it's likely that you will still want some kind of regularization to trim down the number of predictors and kill some of the noise. The Lasso may be helpful here.

(B) Ridge regression can be used in the p > n situation to alleviate singularity issues in the design matrix. This may be useful if sparsity / feature selection is not important. Moreover, ridge regression has a very nice closed form solution that is easily interpreted, and this can be helpful in practice. In essence, you add a positive term to the main diagonal, which improves the regularity of the sample covariance (specifically, it removes vanishing eigenvalues as long as enough regularization is applied).

(I'll leave it the experts to address this one more thoughtfully.)

(C) Soft thresholding and the Lasso are closely related, but not identical. One interpretation of soft thresholding is as the special case of Lasso regression when the predictors are orthogonal, which is of course a restrictive assumption.

Another interpretation of soft thresholding is as the one-at-a-time update in coordinate descent algorithms for the Lasso. I recommend the paper "Pathwise Coordinate Optimization" by Friedman et al for an introduction to these concepts. For a slightly more recent and more general treatment, there is the excellent paper "SparseNet: Coordinate Descent With Nonconvex Penalties" by Mazumder et al.

Answer 2

Lasso does variable selection, whereas ridge is similar to principal components analysis (PCA).. So you use these penalty methods accordingly.. Eg in image processing where you have a lot of similar correlated inputs (pixels) pca is natural and you select the directions that involve the most pixels changing together (throwing away directions in which only a few pixels change together-"noise'). Whereas lasso would be selecting individual pixels from each correlated group of pixels, and not averaging over them as l2/PCA would. If instead you have a whole bunch of heterogeneous inputs (eg predictors for smoking?) where correlation between inputs is either small, or you want to eliminate (to make the model interpretable), then lasso is more appropriate