Applying ridge regression for an underdetermined system of equations?

When $y = X\beta + e$, the least squares problem which imposes a spherical restriction $\delta$ on the value of $\beta$ can be written as $$\begin{array} &\operatorname{min}\ \| y - X\beta \|^2_2 \\ \operatorname{s.t.}\ \ \|\beta\|^2_2 \le \delta^2 \end{array}$$ for an overdetermined system. $\|\cdot\|_2$ is the Euclidean norm of a vector.

The corresponding solution to $\beta$ is given by $$\hat{\beta} = \left(X^TX + \lambda I\right)^{-1}X^T y \ ,$$ which can be derived from the method of Lagrange multipliers ($\lambda$ is the multiplier): $$\mathcal{L}(\beta,\lambda) = \|y-X\beta\|^2_2 + \lambda(\|\beta\|^2_2 - \delta^2)$$

I understand that there is a property that $$\left(X^TX + \lambda I\right)^{-1}X^T = X^T\left(XX^T + \lambda I\right)^{-1} \ .$$ The right hand side resembles the pseudo-inverse of the regressor matrix $X$ in the underdetermined case (with the added regularization parameter, $\lambda$). Does this mean mean that the same expression can be used to approximate $\beta$ for the underdetermined case? Is there a separate derivation for the corresponding expression in the underdetermined case, as the spherical restriction constraint is redundant with the objective function (minimum norm of $\beta$):

$$\begin{array} &\operatorname{min.}\ \| \beta \|_2\\ \operatorname{s.t.}\ X\beta = y \ . \end{array}$$

Starting with the formulation of the ridge regression problem as

$\min \| X\beta -y \|_{2}^{2} + \lambda \| x \|_{2}^{2}$

you can write the problem as

$\min \| A\beta - b \|_{2}^{2}$

where

$A=\left[ \begin{array}{c} X \\ \sqrt{\lambda} I \end{array} \right]$

and

$b=\left[ \begin{array}{c} y \\ 0 \end{array} \right].$

The matrix $A$ has full column rank because of the $\sqrt{\lambda}I$ part. Thus the least squares problem as a unique solution

$\hat{\beta}=(A^{T}A)^{-1}A^{T}b$

Writing this out in terms of $X$ and $y$, and simplifying lots of 0's out, we get

$\hat{\beta}=(X^{T}X+\lambda I)^{-1}X^{T}y$

Nothing in this derivation depends on whether $X$ has more rows or columns, or even on whether $X$ has full rank. This formula is thus applicable to the undetermined case.

It is an algebraic fact that for $\lambda>0$,

$(X^{T}X+\lambda I)^{-1}X^{T}=X^{T}(XX^{T}+\lambda I)^{-1}$

Thus we also have the option of using

$\hat{\beta}=X^{T}(XX^{T}+\lambda I)^{-1}y$.

1. Yes, both formulas work for the undetermined case as well as the over determined case. They also work if $\mbox{rank}(X)$ is less than the minimum of the number of rows and columns of $X$. The second version can be more efficient for problems that are undetermined because $XX^{T}$ is smaller than $X^{T}X$ in that case.

2. I'm not aware of any derivation of the alternative version of the formula that starts with some other damped least squares problem and uses the normal equations. In any case you can derive it in a straight forward fashion using a bit of algebra.

It's possible that you're thinking of the ridge regression problem in the form

$\min \| \beta \|_{2}^{2}$

subject to

$\| X\beta-y \|_{2}^{2} \leq \epsilon.$

However, this version of the ridge regression problem simply leads to the same damped least squares problem $\min \| X\beta -y \|_{2}^{2} + \lambda \| \beta \|_{2}^{2}$.

• It's worth noting what happens in the limit as $\lambda$ goes to 0 if $X$ has full row rank or full column rank. If $X$ has full column rank, then in the limit, you get the pseudoinverse $(X^{T}X)^{-1}X^{T}$. Similarly, if $X$ has full row rank, then in the limit you get the pseudoinverse $X^{T}(XX^{T})^{-1}$. So, this works out as we'd expect. – Brian Borchers Jan 21 '14 at 23:22
• This is a phenomenally comprehensive answer and the derivation from the augmented arrays (plus algebra that I missed) is very satisfying. I wasn't thinking of the ridge regression problem in the form you presented at the end, but it is interesting to see that it leads to the same objective function. A big thanks! – hatmatrix Jan 22 '14 at 0:32
• Thanks. I'll insert a shameless plug here- You can find this (and lots of related material) in the textbook on parameter estimation and inverse problems that I coauthored with Rick Aster and Cliff Thurber. – Brian Borchers Jan 22 '14 at 3:20
• Let me also add that actually computing this matrix inverse is typically not the best way to use this formula. Depending on the size and possible sparsity of $X$ you might be much better off using an iterative scheme or simply using the Cholesky factorization of the matrix $X^{T}X + \lambda I$. – Brian Borchers Jan 22 '14 at 4:32
• Thanks for your suggestions! I appreciate the reference to your book as I have had trouble finding a texbook on this material. Our data size is actually not very large (only that we may have to apply this many times to separate data sets), so may be amenable to the direct inverse, but thanks for the additional pointers! – hatmatrix Jan 22 '14 at 23:22