Least Squares and Pseudoinverses

Replace an unreachable target with its closest column-space projection, interpret the orthogonal residual, and use the pseudoinverse to select the minimum-norm least-squares solution.

When a target lies outside a matrix's column space, the system $A\mathbf{x}=\mathbf{b}$ has no exact solution. Least squares replaces the unreachable target with its closest reachable approximation. The pseudoinverse then provides one consistent rule for choosing the parameters.

An Inconsistent System Still Has a Best Approximation

Suppose one number $x$ is expected to satisfy both

x=1 \qquad\text{and}\qquad x=3.

No value satisfies both equations. In matrix form,

\underbrace{\begin{bmatrix}1\\1\end{bmatrix}}_{A}x =\underbrace{\begin{bmatrix}1\\3\end{bmatrix}}_{\mathbf{b}}.

The reachable predictions are all points $[x,x]^{\mathsf T}$ on a line. The target $[1,3]^{\mathsf T}$ lies outside that line. Least squares chooses the reachable point closest to the target.

This situation is common when several noisy measurements constrain fewer unknown quantities. The equations may disagree slightly even though a useful approximation exists.

The Residual Measures the Remaining Error

For a proposed parameter vector $\mathbf{x}$ , define

\widehat{\mathbf{b}}=A\mathbf{x} \qquad\text{and}\qquad \mathbf{r}=\mathbf{b}-\widehat{\mathbf{b}}.

Here $\widehat{\mathbf{b}}$ is the fitted or predicted output, and $\mathbf{r}$ is the residual. Least squares chooses

\mathbf{x}^{\star} =\underset{\mathbf{x}}{\arg\min}\; \|\mathbf{b}-A\mathbf{x}\|_2^2.

Read this as: “among all parameter vectors $\mathbf{x}$ , choose the one that makes the squared distance between the target $\mathbf{b}$ and prediction $A\mathbf{x}$ as small as possible.”

The notation $\arg\min$ asks for the input at which the expression is smallest, rather than the smallest value itself.

For the scalar example, the objective is

L(x)=(1-x)^2+(3-x)^2.

Expanding and completing the square gives

L(x)=2x^2-8x+10=2(x-2)^2+2,

so the minimum occurs at $x=2$ . The fitted output is $[2,2]^{\mathsf T}$ and the residual is $[-1,1]^{\mathsf T}$ . Least squares does not make an impossible system exact; it makes the squared residual as small as possible.

Exercise: Find a one-parameter least-squares fit

Minimize $(2-x)^2+(6-x)^2$ . What value of $x$ gives the least-squares fit?

Check the fitted value

Compute it first, then check your number.

HintBalance the two residuals

At the midpoint, the two residuals have equal magnitude and opposite signs.

SolutionComplete the square

Expanding gives

(2-x)^2+(6-x)^2=2x^2-16x+40=2(x-4)^2+8.

The nonnegative squared term is smallest at $x=4$ . At this point the two residuals are $-2$ and $2$ , so neither direction of movement can reduce their total squared magnitude.

Least Squares Is an Orthogonal Projection

Every prediction $A\mathbf{x}$ lies in $\operatorname{Col}(A)$ . The closest prediction $A\mathbf{x}^{\star}$ is the orthogonal projection of $\mathbf{b}$ onto that column space.

At the closest point, the residual

\mathbf{r}^{\star}=\mathbf{b}-A\mathbf{x}^{\star}

is orthogonal to every column of $A$ . Writing all those dot products together gives

A^{\mathsf T}\mathbf{r}^{\star}=\mathbf{0}.

Substituting the residual definition produces the normal equations:

A^{\mathsf T}A\mathbf{x}^{\star}=A^{\mathsf T}\mathbf{b}.

The normal equations say that, at the least-squares solution, every column of $A$ has zero dot product with the residual. They describe perpendicularity, not a new kind of average.

The word “normal” refers to perpendicularity: the residual is normal to the column space.

Exercise: Identify the optimal residual direction

At a least-squares solution, how is the residual related to $\operatorname{Col}(A)$ ?

Choose the geometric condition

It is orthogonal to every column of A.

It must lie inside the column space of A.

It must always equal the zero vector.

Select one choice, then check.

HintUse the projection geometry

Draw the shortest segment from the target to the column space.

SolutionThe residual is perpendicular

The fitted output is the orthogonal projection of $\mathbf{b}$ onto the column space. Therefore the displacement from the fit to the target is perpendicular to every column-space direction:

A^{\mathsf T}\mathbf{r}^{\star}=\mathbf{0}.

The Best Prediction May Have Several Parameter Vectors

The fitted output $A\mathbf{x}^{\star}$ is unique because an orthogonal projection onto a subspace is unique. The parameter vector $\mathbf{x}^{\star}$ need not be unique.

If $A$ has a nontrivial null space and $\mathbf{z}\in\operatorname{Null}(A)$ , then

A(\mathbf{x}^{\star}+\mathbf{z}) =A\mathbf{x}^{\star}.

All these parameter vectors produce the same fit and the same residual. A least-squares parameter solution is unique exactly when $A$ has full column rank. In that case $A^{\mathsf T}A$ is invertible and

\mathbf{x}^{\star} =(A^{\mathsf T}A)^{-1}A^{\mathsf T}\mathbf{b}.

This formula explains the solution but is not usually the preferred numerical procedure. Forming $A^{\mathsf T}A$ can worsen conditioning; QR or singular value decomposition is generally more reliable.

Exercise: Recognize nonunique parameters

Suppose $\mathbf{x}^{\star}$ minimizes the squared residual and $\mathbf{z}$ is a nonzero null vector of $A$ . What can be said about $\mathbf{x}^{\star}+\mathbf{z}$ ?

Choose the consequence

It produces the same fitted output and is also a least-squares solution.

It always produces a smaller residual.

It cannot be a solution because z is nonzero.

Select one choice, then check.

HintApply the matrix to the sum

Use linearity and the definition of the null space.

SolutionNull-space movement preserves the fit

Since $A\mathbf{z}=\mathbf{0}$ ,

A(\mathbf{x}^{\star}+\mathbf{z}) =A\mathbf{x}^{\star}+A\mathbf{z} =A\mathbf{x}^{\star}.

The fitted output and residual are unchanged, so the shifted vector is another least-squares solution.

The Pseudoinverse Chooses One Canonical Solution

The Moore–Penrose pseudoinverse, written $A^{+}$ , is defined for every matrix—square or rectangular, full rank or rank deficient. The vector

\mathbf{x}^{+}=A^{+}\mathbf{b}

has two linked properties:

it minimizes $\|\mathbf{b}-A\mathbf{x}\|_2$ ;
among all vectors with that minimum residual, it has the smallest Euclidean norm $\|\mathbf{x}\|_2$ .

Thus the pseudoinverse handles both difficulties:

if the target is unreachable, it chooses a closest reachable prediction;
if several parameter vectors give that prediction, it chooses the minimum-norm one.

When a square matrix is invertible, $A^{+}=A^{-1}$ . The pseudoinverse is not an ordinary inverse for every matrix; in general, neither $A^{+}A$ nor $AA^{+}$ must be the identity. Instead, these products act as projections onto the appropriate retained subspaces.

Exercise: Choose among equally good fits

Several parameter vectors produce the same minimum least-squares residual. Which one does $A^{+}\mathbf{b}$ select?

Choose the selection rule

The solution with the smallest Euclidean norm

The solution with the largest entries

Whichever solution was discovered first

Select one choice, then check.

HintRecall the second optimization criterion

First minimize the residual; then minimize the parameter norm among ties.

SolutionUse the minimum-norm solution

The pseudoinverse first attains the smallest possible residual and then selects, among all equally good fits, the vector with minimum $\|\mathbf{x}\|_2$ .

Singular Values Explain the Pseudoinverse

The later singular value decomposition lesson will factor a matrix as

A=U\Sigma V^{\mathsf T}.

In that coordinate system, the pseudoinverse reciprocates nonzero singular values and leaves zero singular values at zero:

A^{+}=V\Sigma^{+}U^{\mathsf T}.

A zero singular value represents a direction erased by the matrix. Replacing it with $1/0$ would be undefined and would pretend to recover information that the output does not contain.

Exercise: Interpret a zero singular value

Why does the pseudoinverse leave the reciprocal of a zero singular value at zero rather than attempting to compute $1/0$ ?

Choose the reason

The corresponding input direction was erased and cannot be recovered.

Zero is defined to mean a small positive value.

Transposition has already recovered that direction.

Select one choice, then check.

HintTrack the lost direction

Every magnitude along that input direction produces the same zero output component.

SolutionDo not invent erased information

A zero singular value collapses an input direction to zero. Because the output contains no evidence of the original magnitude, no inverse-like operation can reconstruct it uniquely.

Compare least squares and the pseudoinverse

Edit the matrix or target. Both methods produce a least-squares fit; the pseudoinverse also remains defined for rank-deficient matrices.

Ready to run.

The repeated columns make the parameter vector nonunique. The pseudoinverse splits the shared contribution evenly, giving the minimum-norm solution. The final output confirms that the residual is orthogonal to both columns.

Before Using Least Squares

Separate three objects: the parameter vector $\mathbf{x}$ , the fitted output $A\mathbf{x}$ , and the residual $\mathbf{b}-A\mathbf{x}$ . Check whether the target is exactly reachable, whether the parameters are unique, and whether a minimum-norm selection is appropriate. In numerical work, use a least-squares solver rather than explicitly forming $(A^{\mathsf T}A)^{-1}$ .

The next lesson studies eigenvectors: special directions that a square matrix keeps on the same line. That viewpoint begins a different route into matrix structure and repeated transformations.