Pseudoinverses for Inconsistent Linear Systems

Why Use a Pseudoinverse?

A linear system $Ax=b$ need not have an exact solution. For instance, there may be more equations than unknowns, or the equations may contradict one another. Even when exact solutions exist, there may be many of them if $A$ is rank-deficient or has more columns than rows. The Moore–Penrose inverse addresses both situations: it gives a solution with the smallest residual when exact equality is impossible, and among all solutions with that residual it selects one with the smallest Euclidean norm.

Let $A$ be an $m\times n$ real matrix and $b\in\mathbb R^m$. The least-squares problem is to minimize $\|Ax-b\|_2$ over $x\in\mathbb R^n$. The residual convention here is $r=b-Ax$. The key geometric idea is that the fitted vector $Ax$ lies in the column space of $A$, so the best fit is the orthogonal projection of $b$ onto that space.

Definition: The Moore–Penrose inverse of $A$, denoted $A^+$, is the unique $n\times m$ matrix satisfying $$ AA^+A=A,\qquad A^+AA^+=A^+,\qquad (AA^+)^T=AA^+,\qquad (A^+A)^T=A^+A. $$ The matrices $AA^+$ and $A^+A$ are the orthogonal projection matrices onto $\operatorname{Col}(A)\subseteq\mathbb R^m$ and $\operatorname{Col}(A^T)\subseteq\mathbb R^n$, respectively.

These projection properties can be seen directly from a singular value decomposition. If $A$ has rank $r>0$, write its compact singular value decomposition as $A=U_r\Sigma_r V_r^T$, where $U_r$ and $V_r$ have orthonormal columns and $\Sigma_r$ is diagonal with positive entries. Then

A^+=V_r\Sigma_r^{-1}U_r^T,\qquad AA^+=U_rU_r^T,\qquad A^+A=V_rV_r^T.

The last two matrices are symmetric and idempotent, and their ranges are the columns of $U_r$ and $V_r$. When $A=0$, take $A^+=0$; both projections are zero. Thus these statements also cover rank zero. The pseudoinverse is not an ordinary inverse in general: it is defined for rectangular and singular matrices as well.

The Least-Squares Solution and Its Geometry

Theorem: For any real $m\times n$ matrix $A$ and $b\in\mathbb R^m$, $x_*=A^+b$ minimizes $\|Ax-b\|_2$. Every least-squares minimizer has the form $$ x=A^+b+(I_n-A^+A)z,\qquad z\in\mathbb R^n. $$ Among these minimizers, $A^+b$ is the unique one with minimum Euclidean norm. The fitted vector is $AA^+b$, and its residual $b-AA^+b$ is orthogonal to $\operatorname{Col}(A)$.

Proof. Use the compact singular value decomposition above; when $r=0$, the same argument holds with all column-space projections equal to zero. Set $P=U_rU_r^T=AA^+$. Since the columns of $U_r$ are an orthonormal basis for $\operatorname{Col}(A)$, $Pb$ is the orthogonal projection of $b$ onto $\operatorname{Col}(A)$. Also,

Ax_*=AA^+b=Pb,\qquad b-Pb\perp\operatorname{Col}(A).

For any $x$, $Pb-Ax$ belongs to $\operatorname{Col}(A)$, while $b-Pb$ is orthogonal to that space. Since $b-Ax=(b-Pb)+(Pb-Ax)$, the Pythagorean theorem gives

\|b-Ax\|_2^2=\|b-Pb\|_2^2+\|Pb-Ax\|_2^2 \geq \|b-Pb\|_2^2.

Equality holds exactly when $Ax=Pb=Ax_*$. Consequently $x$ is a least-squares minimizer exactly when $A(x-x_*)=0$, or $x-x_*\in\operatorname{Null}(A)$. The projection $A^+A=V_rV_r^T$ projects onto $\operatorname{Col}(A^T)$, whose orthogonal complement is $\operatorname{Null}(A)$. Therefore $I_n-A^+A$ projects onto $\operatorname{Null}(A)$, and all minimizers are precisely

x=x_*+(I_n-A^+A)z,\qquad z\in\mathbb R^n.

Finally, $x_*=A^+b=V_r\Sigma_r^{-1}U_r^Tb$ belongs to $\operatorname{Col}(A^T)$, so it is orthogonal to every vector in $\operatorname{Null}(A)$. For any least-squares minimizer $x=x_*+v$ with $v\in\operatorname{Null}(A)$,

\|x\|_2^2=\|x_*\|_2^2+\|v\|_2^2\geq\|x_*\|_2^2.

Equality requires $v=0$, proving that $A^+b$ is the unique minimum-norm minimizer. $\square$

The theorem separates two kinds of projection. $AA^+$ acts on the data vector $b$ in $\mathbb R^m$: it projects onto the vectors that the model can fit. $A^+A$ acts on a candidate parameter vector in $\mathbb R^n$: it projects onto the row space, the part of the parameter space that the data can identify. The null space consists of directions that change $x$ without changing $Ax$.

Worked Examples

Worked Example: An Inconsistent System with One Unknown

Take $A=\begin{bmatrix}1\\1\end{bmatrix}$ and $b=\begin{bmatrix}1\\3\end{bmatrix}$. The equations ask one number $x$ to equal both 1 and 3, so there is no exact solution. Since $A^TA=2$, the pseudoinverse is $A^+=(A^TA)^{-1}A^T=\begin{bmatrix}1/2&1/2\end{bmatrix}$. Thus

x_*=A^+b=\frac12(1)+\frac12(3)=2,\qquad Ax_*=\begin{bmatrix}2\\2\end{bmatrix}.

The projection onto $\operatorname{Col}(A)$, the span of $\begin{bmatrix}1\\1\end{bmatrix}$, is $AA^+=\frac12\begin{bmatrix}1&1\\1&1\end{bmatrix}$. Hence $AA^+b=\begin{bmatrix}2\\2\end{bmatrix}$, as calculated. The residual is $b-Ax_*=\begin{bmatrix}-1\\1\end{bmatrix}$, and its inner product with the column of $A$ is $-1+1=0$. Its squared norm is $1+1=2$. The orthogonal projection therefore verifies both the fitted vector and the least-squares residual.

Worked Example: A Rank-Deficient Inconsistent System

Let $A=\begin{bmatrix}1&1\\2&2\end{bmatrix}$ and $b=\begin{bmatrix}1\\3\end{bmatrix}$. The two columns of $A$ are identical, so $A$ has rank one. A compact singular value decomposition has $u=\frac1{\sqrt5}\begin{bmatrix}1\\2\end{bmatrix}$, $v=\frac1{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}$, and singular value $\sqrt{10}$. Thus $A^+=v(\sqrt{10})^{-1}u^T$, giving

A^+=\begin{bmatrix}1/10&2/10\\1/10&2/10\end{bmatrix},\qquad A^+b=\begin{bmatrix}7/10\\7/10\end{bmatrix}.

The two projection matrices are $AA^+=\begin{bmatrix}1/5&2/5\\2/5&4/5\end{bmatrix}$ and $A^+A=\begin{bmatrix}1/5&1/5\\1/5&1/5\end{bmatrix}$. Applying the first to $b$ gives $\begin{bmatrix}7/5\\14/5\end{bmatrix}$. Direct multiplication confirms $A(A^+b)=\begin{bmatrix}7/5\\14/5\end{bmatrix}$. The residual is $\begin{bmatrix}-2/5\\1/5\end{bmatrix}$, whose inner product with $\begin{bmatrix}1\\2\end{bmatrix}$, a basis for the column space, is $-2/5+2/5=0$. Its squared norm is $4/25+1/25=1/5$.

More generally, $Ax=\begin{bmatrix}x_1+x_2\\2(x_1+x_2)\end{bmatrix}$, so the fitted vector above requires $x_1+x_2=7/5$. Every least-squares minimizer is $\begin{bmatrix}7/10+t\\7/10-t\end{bmatrix}$. Its squared norm is $(7/10+t)^2+(7/10-t)^2=49/50+2t^2$, which is uniquely smallest at $t=0$. This verifies why the pseudoinverse selects the minimum-norm minimizer even though the least-squares solution is not unique.

Worked Example: An Underdetermined System with Exact Solutions

Let $A=\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}$ and $b=\begin{bmatrix}2\\1\end{bmatrix}$. There are two equations and three unknowns. Because $AA^T=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ is invertible, $A^+=A^T(AA^T)^{-1}$. Since $(AA^T)^{-1}=\frac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}$, multiplication gives

A^+= \begin{bmatrix} 2/3&-1/3\\ 1/3&1/3\\ -1/3&2/3 \end{bmatrix}, \qquad A^+b=\begin{bmatrix}1\\1\\0\end{bmatrix}.

Here $AA^+=I_2$, so $AA^+b=b$: the residual is zero and the solution is exact. The null space of $A$ is spanned by $n=\begin{bmatrix}1\\-1\\1\end{bmatrix}$, since $An=0$. Also, $A^+A=I_3-nn^T/3$, the projection onto the plane perpendicular to $n$. The proposed solution is perpendicular to $n$, because $\begin{bmatrix}1&1&0\end{bmatrix}n=0$. All exact solutions are $\begin{bmatrix}1\\1\\0\end{bmatrix}+t n$, and their squared norms are $2+3t^2$. Thus $t=0$ uniquely minimizes the norm, in agreement with the projection onto the row space.

When the Pseudoinverse Matters

In statistical work, a least-squares fit is a projection of the observed response vector onto the space of fitted values available under the design matrix. If the design matrix has redundant columns, different coefficient vectors may yield the same fitted values. The pseudoinverse provides a precise convention for choosing one: the coefficient vector of minimum Euclidean norm. This convention is useful for defining a solution, but it does not make all coefficients individually identifiable. Components in the null space remain invisible to the fitted values.

The two projections also provide practical checks. For a proposed least-squares fit, verify that $AA^+b$ lies in $\operatorname{Col}(A)$ and that $b-AA^+b$ is orthogonal to that column space. For the minimum-norm property, verify that $A^+b$ lies in $\operatorname{Col}(A^T)$, perpendicular to $\operatorname{Null}(A)$. These checks distinguish the geometry of the fit from the choice among coefficient vectors.

Common Mistake

Pitfall: A common error is to treat $A^+b$ as an exact solution of $Ax=b$ for every $A$ and $b$. In general, $AA^+b$ is the projection of $b$ onto $\operatorname{Col}(A)$, which equals $b$ only when $b\in\operatorname{Col}(A)$. The correction is to check the residual $b-AA^+b$: it is always orthogonal to the column space, but it need not be zero.

Check Your Understanding

Use the projection and minimum-norm interpretations to answer the following.

For an arbitrary $A$, what space does $AA^+$ project onto, and in which space does it act?
Why is $b-AA^+b$ orthogonal to every column of $A$?
Describe all least-squares minimizers using $A^+b$ and the null space of $A$.
When does the pseudoinverse solution $A^+b$ solve $Ax=b$ exactly?
In the underdetermined example, why does adding a null-space vector preserve the fitted values but not generally preserve the solution norm?