Regularized Least-Squares Problem

L. El Ghaoui

Regularized Least-Squares Problem

Regularized least-squares
Expression as an ordinary LS problem
Solution

Regularized least-squares

In the case when the matrix $A$ in the OLS problem is not full column rank, the closed-form solution cannot be applied. A remedy often used in practice is to transform the original problem into one where the full column rank property holds.

The regularized least-squares problem has the form

$\min\limits_x ||Ax-y||_2^2+\lambda||x||_2^2.$

where $\lambda > 0$ is a (usually small) parameter.

Expression as an ordinary LS problem

The regularized problem can be expressed as an ordinary least-squares problem, where the data matrix is full column rank. Indeed, the above problem can be written as the ordinary LS problem

$\min\limits_x ||\tilde{A}x-\tilde{y}||_2^2,$

where

$\tilde{A} := \begin{pmatrix} A\\ \sqrt{\lambda} I_n \end{pmatrix}, \tilde{y} := \begin{pmatrix} y\\ 0 \end{pmatrix} .$

The presence of the identity matrix in the $(m+n) \times n$ matrix $\tilde{A}$ ensures that it is full (column) rank.

Solution

Since the data matrix in the regularized LS problem has full column rank, the formula seen here applies. The solution is unique and given by

$x^*=(\tilde{A}^T\tilde{A})^{-1}\tilde{A}^T\tilde{y}=(A^TA+\lambda I_n)^{-1}A^Ty.$

For $\lambda = 0$ , we recover the ordinary LS expression that is valid when the original data matrix is full rank.

The above formula explains one of the motivations for using regularized least-squares in the case of a rank-deficient matrix $A$ : if $\lambda > 0$ , but is small, the above expression is still defined, even if $A$ is rank-deficient.

Regularized Least-Squares Problem

Regularized least-squares

Expression as an ordinary LS problem

Solution

License

Share This Book