In modern data science, we routinely confront regimes where the number of features vastly exceeds the number of observations ($p gg n$)—such as genomics with 20,000 genes measured across 100 patients. In this underdetermined regime, ordinary least squares has infinitely many solutions that fit training data with zero error while catastrophically overfitting. To tame underdetermined ill-posed problems, machine learning relies on Regularization: penalizing parameter norms to enforce smoothness, energy minimization, or exact sparse feature selection.
1. The Ill-Posed Inverse Problem and Shrinkage
Consider linear regression $y = X w + epsilon$ with design matrix $X in mathbb{R}^{n times p}$. When $p > n$, the Gram matrix $X^T X$ has rank at most $n$, rendering it strictly non-invertible. Infinitely many parameter vectors lie in the null space $text{null}(X)$, causing the variance of the unregularized ordinary least squares estimator to explode to infinity.
Regularization stabilizes the inversion by adding a penalization term $Omega(w)$ parameterized by regularization strength $lambda > 0$:
$$min_w frac{1}{2n} |y – X w|_2^2 + lambda Omega(w)$$
2. $L_2$ Ridge Regularization (Tikhonov)
Introduced by Andrey Tikhonov (1943) and popularized in statistics by Hoerl & Kennard (1970), Ridge Regression penalizes the squared Euclidean ($L_2$) norm: $Omega(w) = frac{1}{2} |w|_2^2 = frac{1}{2} sum_{j=1}^p w_j^2$.
Differentiating the penalized objective:
$$nabla_w left[ frac{1}{2n} |y – X w|_2^2 + frac{lambda}{2} |w|_2^2 right] = -frac{1}{n} X^T (y – X w) + lambda w = 0$$
Solving for $w$ yields the celebrated closed-form estimator:
$$hat{w}_{text{Ridge}} = left( X^T X + nlambda I_p right)^{-1} X^T y$$
The term $nlambda I_p$ shifts the eigenvalues of $X^T X$ positively: $lambda_i(X^T X + nlambda I) = sigma_i^2 + nlambda > 0$. The matrix becomes strictly positive definite and stably invertible. In spectral terms, Ridge acts as a continuous low-pass shrinkage filter, dampening coordinates corresponding to small singular values while leaving dominant directions intact.
3. $L_1$ Lasso Regularization & Sparse Feature Selection
While Ridge shrinks coefficients asymptotically toward zero, it never sets any coefficient strictly to zero: $hat{w}_j ne 0$. In 1996, Robert Tibshirani introduced the Lasso (Least Absolute Shrinkage and Selection Operator), penalizing the absolute sum ($L_1$ norm):
$$min_w frac{1}{2n} |y – X w|_2^2 + lambda |w|_1, quad text{where} quad |w|_1 = sum_{j=1}^p |w_j|$$
Lasso exhibits a profound mathematical property: for sufficiently large $lambda$, it drives a subset of coefficients strictly to zero, performing simultaneous estimation and automated feature selection.
4. The Geometric Origin of Sparsity
Why does the $L_1$ norm produce exact zeros while $L_2$ does not? Formulating both problems in equivalent Karush-Kuhn-Tucker constrained form:
$$min_w frac{1}{2n} |y – X w|_2^2 quad text{subject to} quad Omega(w) le C$$
Geometrically, the solution is the point of tangency where the expanding ellipsoidal level sets of the quadratic loss first touch the constraint boundary $Omega(w) le C$:
- The $L_2$ Ball ($|w|_2^2 le C$): A smooth sphere with isotropic curvature. The loss contours touch the sphere at a generic point along the curved surface where both $w_1 ne 0$ and $w_2 ne 0$.
- The $L_1$ Ball ($|w|_1 le C$): A cross-polytope (a diamond in $mathbb{R}^2$, an octahedron in $mathbb{R}^3$) characterized by sharp vertices aligned strictly along the coordinate axes. Because these vertices stick out furthest, the expanding loss contours are overwhelmingly likely to touch a vertex first. At any coordinate vertex, all other coordinates are identically zero ($w_j = 0$), inducing structural sparsity!
5. Proximal Gradient & Soft-Thresholding
Because the $L_1$ norm is non-differentiable at $w_j = 0$, standard gradient descent cannot be applied directly. Instead, modern optimization uses the Proximal Gradient Operator. Under an orthogonal design ($X^T X = I$), the Lasso solution reduces to the exact Soft-Thresholding Operator $mathcal{S}_{lambda}(z)$:
$$hat{w}_j = mathcal{S}_{lambda}(w_j^{text{OLS}}) = text{sign}(w_j^{text{OLS}}) max(0, |w_j^{text{OLS}}| – lambda)$$
Any coefficient whose magnitude $|w_j^{text{OLS}}|$ is less than threshold $lambda$ is truncated strictly to zero, while larger coefficients are shrunk toward zero by constant magnitude $lambda$. By uniting convex optimization with high-dimensional sparsity, $L_1$ regularization established the foundation of modern compressive sensing and sparse statistical learning.
