Linear Least Squares Problem

From an inconsistent system to a best fit

Let $A \in \mathbb{R}^{m \times n}$ , $x \in \mathbb{R}^n$ , and $b \in \mathbb{R}^m$ . Consider the following system.

Ax=b

If $b$ does not belong to the column space of $A$ , this system has no exact solution. This commonly happens when a model is fitted to $noisy measurements$ or when an overdetermined system contains more equations than unknowns and those equations are inconsistent.

If no vector $x$ satisfies $Ax=b$ exactly, define the residual

e(x)=Ax-b

We seek the vector $x$ that produces the smallest residual. The standard linear least-squares problem is written as follows.

\hat{x}\in\operatorname*{arg\,min}_{x\in\mathbb{R}^n}\|Ax-b\|_2^2

Because the residual has $m$ components, the objective expands to

\|Ax-b\|_2^2=\sum_{i=1}^{m}(Ax-b)_i^2

Squaring makes every contribution nonnegative and penalizes a large residual component more strongly than a small one.

The geometric condition

The vector $A\hat{x}$ is the point in $\operatorname{col}(A)$ closest to $b$ in Euclidean distance. At the optimum, $the residual is orthogonal to every column$ of $A$ :

A^{\mathsf T}(A\hat{x}-b)=0

The second equation is called the $normal equation$ .

Orthogonal projection in a least-squares problem

The blue vector ends at

A\hat{x}

, the orange vector ends at

b

, and the purple vector is the residual

A\hat{x}-b

$x$: $[0, 3]$
$y$: $[0, 3]$
$z$: $[0, 6]$
Lines: 3

The diagram labels the target vector $b$ , the projected point $A\hat{x}$ , and the residual $A\hat{x}-b$ between them. The blue vector $A\hat{x}$ lies in the column space. The orthogonality condition above proves that it is the nearest point in that space to $b$ .

Fitting One Constant to Three Observations

Suppose one constant $x$ must fit the three observations $1$ , $2$ , and $6$ . Use the following matrix and vector.

A=\begin{pmatrix}1\\1\\1\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\\6\end{pmatrix}

The objective function for this example is

\begin{aligned} F(x) &=(x-1)^2+(x-2)^2 \\ &\quad{}+(x-6)^2 \end{aligned}

Setting the $derivative to zero$ gives $\hat{x}=3$ . The fitted vector and residual are

A\hat{x}=\begin{pmatrix}3\\3\\3\end{pmatrix}

The residual components sum to zero, so

A^{\mathsf T}(A\hat{x}-b)=2+1-3=0

The zero result satisfies the normal equation.

Other residual norms

The norm determines what $kind of error$ the fit prioritizes.

Objective	What it controls
$\displaystyle\min_x\\|Ax-b\\|_2^2=\min_x\sum_{i=1}^{m}(Ax-b)_i^2$	Penalizes large residuals quadratically and gives the usual least-squares projection.
$\displaystyle\min_x\\|Ax-b\\|_1=\min_x\sum_{i=1}^{m}\lvert(Ax-b)_i\rvert$	Uses a linear penalty, so an occasional large residual has less influence than under squared loss.
$\displaystyle\min_x\\|Ax-b\\|_\infty=\min_x\max_{1\le i\le m}\lvert(Ax-b)_i\rvert$	Minimizes the worst absolute residual.

The $\ell_1$ and $\ell_\infty$ formulations can be rewritten as linear programs. Their suitability still depends on the data-generating process and the error criterion that matters for the application.

For the same observations 1, 2, and 6, the norm changes the fitted constant. Least squares chooses the mean, absolute loss chooses the median, and the smallest maximum error balances distances to the two extremes.

Criterion	Optimal constant	Minimum objective
$\ell_2^2$	$(1+2+6)/3=3$	$2^2+1^2+(-3)^2=14$
$\ell_1$	$2$	$1+0+4=5$
$\ell_\infty$	$(1+6)/2=7/2$	$\max(5/2,3/2,5/2)=5/2$

Choosing a Stable Numerical Method

If $A$ has $full column rank$ , the least-squares minimizer is unique. The normal equation then implies

\hat{x}=(A^{\mathsf T}A)^{-1}A^{\mathsf T}b

This identity characterizes the unique minimizer when $A$ has full column rank. Do not compute it by explicitly forming the inverse. Choose the numerical method from the rank and conditioning:

use a $\mathrm{QR}$ factorization for a stable full-rank least-squares solve
use an $\mathrm{SVD}$ when rank deficiency or ill-conditioning matters
use the pseudoinverse to select the minimum-norm solution when minimizers are not unique

There is also a precise statistical interpretation. Consider the following model.

b=Ax_*+\varepsilon,\qquad \varepsilon\sim\mathcal{N}(0,\sigma^2I),\quad \sigma^2>0

If $A$ is fixed and the Gaussian errors are independent with common variance, least squares gives the maximum-likelihood estimator of $x_*$ . Correlated errors or errors with unequal variance require weights that reflect the error covariance.