Linear Models | LA 101

The Matrix Perspective on Machine Learning

Machine learning models ingest data — thousands or millions of examples, each described by many features. The first step in almost every algorithm is to organize this data into a design matrix X, where each row is one example and each column is one feature. When the model is linear, the entire prediction task reduces to a sequence of matrix operations.

This is not a mere notational convenience. The matrix structure reveals which operations are parallelizable, which solutions are exact, what the geometry of the problem looks like, and why certain regularization strategies work. Every formula we derive in this lesson has an elegant geometric interpretation in the column space of X.

Linear Regression: The Normal Equations

Given n training examples with p features each, linear regression models the output as a linear combination of the features:

Linear Regression Model

\mathbf{y} = X\boldsymbol{\beta} + \boldsymbol{\varepsilon}

X is the n×p design matrix, β is the p-dimensional coefficient vector, and ε is the n-dimensional noise vector. Each row xᵢᵀ β gives the predicted value for example i. The goal is to find β that minimizes the sum of squared residuals.

We want to minimize the residual sum of squares: RSS(β) = ‖y − Xβ‖². This is the squared distance from the response vector y to the vector Xβ in ℝⁿ. Geometrically, the minimizer is the projection of y onto the column space of X — the closest point in col(X) to y.

Setting the gradient to zero yields the normal equations: XᵀXβ = Xᵀy. When XᵀX is invertible (columns of X are linearly independent), the unique least-squares solution is:

OLS Solution

\hat{\boldsymbol{\beta}} = (X^T X)^{-1} X^T \mathbf{y}

The hat matrix H = X(XᵀX)⁻¹Xᵀ is the orthogonal projection onto col(X). The fitted values ŷ = Hy are the projection of y onto the column space of X. When columns are not independent, the Moore-Penrose pseudoinverse X⁺ = (XᵀX)⁺Xᵀ replaces (XᵀX)⁻¹Xᵀ.

Geometric Interpretation

Linear regression is orthogonal projection. The residual vector r = y − ŷ is perpendicular to every column of X — that is, Xᵀr = 0. This is exactly the normal equations rearranged. The projected vector ŷ is the unique point in col(X) closest to y.

Ridge Regression: L2 Regularization

When p is large relative to n, or when columns of X are nearly collinear, the matrix XᵀX becomes ill-conditioned: small perturbations in y cause large swings in the OLS estimate β̂. Ridge regression stabilizes the solution by adding a penalty on the magnitude of β:

Ridge Objective and Solution

\hat{\boldsymbol{\beta}}_{\text{ridge}} = (X^T X + \lambda I)^{-1} X^T \mathbf{y}

The ridge solution adds λI to the potentially singular XᵀX, guaranteeing invertibility for any λ > 0. Larger λ shrinks all coefficients toward zero. The matrix (XᵀX + λI) has the same eigenvectors as XᵀX but eigenvalues shifted up by λ — this directly improves the condition number.

The SVD of X = UΣVᵀ makes the geometry of ridge regression transparent. The OLS solution expands β̂ = Σₖ (uₖᵀy / σₖ) vₖ — contributions from directions with small singular values σₖ get amplified if σₖ is tiny. Ridge replaces σₖ with σₖ²/(σₖ² + λ), shrinking each component smoothly rather than truncating it. This is closely related to truncated SVD, which simply zeroes out components below a threshold.

Lasso Regression: L1 Regularization

Lasso (Least Absolute Shrinkage and Selection Operator) replaces the L2 penalty with an L1 penalty on the coefficients. Two norms are in play here, so it is worth naming them side by side: the L2 (Euclidean) norm ‖β‖₂ = √(Σⱼ βⱼ²) is the straight-line length you already know from Module 6, while the L1 (taxicab) norm ‖β‖₁ = Σⱼ |βⱼ| simply adds up the absolute values. Both measure "how big" a coefficient vector is, but they penalize differently — and that difference is what makes lasso sparse.

Lasso Objective

\hat{\boldsymbol{\beta}}_{\text{lasso}} = \underset{\boldsymbol{\beta}}{\arg\min}\; \|\mathbf{y} - X\boldsymbol{\beta}\|^2 + \lambda \|\boldsymbol{\beta}\|_1

The L1 constraint ‖β‖₁ = Σⱼ|βⱼ| creates a diamond-shaped feasible region in coefficient space. Because the corners of the diamond lie on the coordinate axes, the optimal solution often occurs at a corner — exactly setting some coefficients to zero. Lasso performs automatic variable selection.

Unlike ridge regression, lasso does not have a closed-form solution because the L1 norm is not differentiable at zero. It is solved by convex optimization algorithms such as coordinate descent or the LARS algorithm. The key structural insight is geometric: the L1 ball is a polytope (diamond in 2D, cross-polytope in higher dimensions) whose extreme points lie on coordinate axes, promoting sparsity. The L2 ball is smooth everywhere, so the optimum rarely occurs at a sparse point.

Ridge vs. Lasso: A Comparison

Ridge: closed-form solution, all coefficients shrink but none exactly zero, better when all features are relevant
Lasso: no closed-form, many coefficients set exactly to zero (sparse), better for feature selection when most features are irrelevant
Elastic Net: convex combination of both penalties — combines sparsity with stability

The Kernel Trick

Linear regression and classification assume the decision boundary or regression function is linear in the features. When this is too restrictive, one approach is to map the data to a higher-dimensional feature space where linear models work better. The kernel trick avoids computing this high-dimensional mapping explicitly.

Suppose we map each data point xᵢ to a feature vector φ(xᵢ) in some (possibly infinite-dimensional) space. The kernel function k(xᵢ, xⱼ) = φ(xᵢ)ᵀφ(xⱼ) computes the inner product in this feature space from the original inputs — without ever computing φ explicitly. Common kernels include:

Polynomial kernel: k(x,z) = (xᵀz + c)^d — maps to degree-d polynomial features
RBF / Gaussian kernel: k(x,z) = exp(−‖x−z‖²/2σ²) — infinite-dimensional feature space
Linear kernel: k(x,z) = xᵀz — recovers standard linear models

The kernel matrix K (where Kᵢⱼ = k(xᵢ, xⱼ)) replaces XᵀX or XXᵀ in the normal equations. Any algorithm that only accesses the data through inner products can be "kernelized" — including regression, PCA, and SVMs.

Mercer's Theorem

A function k(x, z) is a valid kernel if and only if the n×n kernel matrix K is symmetric positive semi-definite for any choice of n data points. This guarantees the existence of a feature map φ and ensures that kernel algorithms correspond to convex optimization problems.

Support Vector Machines: The Linear Algebra View

A support vector machine (SVM) finds the maximum-margin hyperplane separating two classes. In the linearly separable case, the hyperplane is defined by a weight vector w and bias b such that wᵀxᵢ + b ≥ 1 for class +1 and wᵀxᵢ + b ≤ −1 for class −1. The margin width is 2/‖w‖, so maximizing the margin is equivalent to minimizing ‖w‖²/2:

Hard-Margin SVM

\min_{\mathbf{w},b}\; \tfrac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.} \quad y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1 \; \forall i

This is a quadratic program (QP): minimize a quadratic objective over linear inequality constraints. The dual formulation reveals that the solution depends only on inner products xᵢᵀxⱼ, enabling kernelization. The support vectors are the training points for which αᵢ > 0 in the dual — the points closest to the decision boundary.

The Lagrangian dual of the SVM QP is: maximize Σᵢ αᵢ − ½ Σᵢⱼ αᵢ αⱼ yᵢ yⱼ (xᵢᵀxⱼ), subject to αᵢ ≥ 0 and Σᵢ αᵢ yᵢ = 0. Since the data appears only through inner products xᵢᵀxⱼ, replacing these with a kernel k(xᵢ, xⱼ) gives the kernel SVM — a linear classifier in the feature space φ(x), which may be nonlinear in the original input space.

Soft-Margin SVM

Real data is rarely linearly separable. The soft-margin SVM introduces slack variables ξᵢ ≥ 0 that allow some training points to violate the margin, with a cost penalized by the hyperparameter C. The objective becomes min ½‖w‖² + C Σᵢ ξᵢ — a classic bias-variance tradeoff: large C means low training error (low bias, high variance); small C allows more margin violations (high bias, low variance).

Key Takeaways

Linear regression is orthogonal projection onto the column space of the design matrix X, with the closed-form solution β̂ = (XᵀX)⁻¹Xᵀy. Ridge regression adds λI to stabilize the solution, with each SVD component shrunk by σ²/(σ²+λ). Lasso uses an L1 penalty whose non-smooth geometry naturally produces sparse solutions — automatic feature selection. The kernel trick replaces explicit high-dimensional feature maps with kernel functions k(xᵢ,xⱼ), enabling nonlinear models that still reduce to linear algebra on the kernel matrix. SVMs find the maximum-margin hyperplane via a QP whose dual depends only on inner products — making them naturally kernelizable. Support vectors are the training points that define the boundary.