The pseudo-inverse

A matrix that flattens the plane can’t be undone. Watch the best attempt: it brings back everything that wasn’t crushed.

Undo what can be undone

The matrix in the picture, $\mathbf{B}_2=\begin{bmatrix}1&1\\2&2\end{bmatrix}$, sends every point onto the line of $(1,2)$. Points that differ along the null direction, $(1,-1)$, land in the same place, so no matrix can tell them apart afterwards. There is no inverse, as The inverse matrix showed for every flattening map.

But some of the information survives. The SVD of The singular value decomposition says exactly what: $\mathbf{B}_2$ takes the direction $\mathbf{v}_1=(1,1)/\sqrt2$, stretches it by $\sigma_1=\sqrt{10}$, and lays it along $\mathbf{u}_1=(1,2)/\sqrt5$. Everything along the other direction is multiplied by $\sigma_2=0$ and lost. The best undo reverses the part that survived and leaves the lost part at zero.

Build it from the SVD

In $\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top$, swap the two turns and replace each nonzero singular value by its reciprocal, leaving the zeros as zeros. That gives the pseudo-inverse, in full the Moore–Penrose pseudo-inverse:

Here $\boldsymbol{\Sigma}^+$ holds $1/\sigma_k$ where $\sigma_k>0$ and 0 elsewhere, transposed to fit. When $\mathbf{A}$ is invertible nothing is zero, and $\mathbf{A}^+=\mathbf{A}^{-1}$.

For $\mathbf{B}_2$ there is one piece:

What it does and doesn’t undo

Multiply both ways. $\mathbf{B}_2^+\mathbf{B}_2=\tfrac12\begin{bmatrix}1&1\\1&1\end{bmatrix}$, the projection onto the line of $(1,1)$ from Projections. And $\mathbf{B}_2\mathbf{B}_2^+=\tfrac15\begin{bmatrix}1&2\\2&4\end{bmatrix}$, the projection onto the line of $(1,2)$. Neither is $\mathbf{I}$.

The shortest least-squares answer

Ask $\mathbf{B}_2\mathbf{x}=\mathbf{b}$ with $\mathbf{b}=(3,6)$, which lies on the line of outputs. Every $\mathbf{x}$ with $x_1+x_2=3$ solves it: a whole line of answers, as in The complete solution. The pseudo-inverse picks one:

Its length is 2.121, shorter than $(3,0)$ or any other answer. It lies in the row space, with no part along the null direction, and adding a null part can only make an answer longer.

Now a target off the line, $\mathbf{b}=(1,0)$. No $\mathbf{x}$ reaches it. The best that can be done is to reach the closest output, the foot of $(1,0)$ on the line of $(1,2)$, which is $\tfrac15(1,2)=(0.2,\,0.4)$, as in Least squares. The pseudo-inverse gives $\mathbf{x}^+=\mathbf{B}_2^+(1,0)=(0.1,\,0.1)$, and indeed $\mathbf{B}_2\mathbf{x}^+=(0.2,\,0.4)$.

So in every case $\mathbf{A}^+\mathbf{b}$ is the shortest of all the least-squares answers. When the columns of $\mathbf{A}$ are independent there is only one, and $\mathbf{A}^+=(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top$, the formula of the least-squares page.

Ridge: damping the weak directions

Trouble starts when a singular value is not zero but tiny. Say $\sigma=(2,\ 0.01)$. The pseudo-inverse multiplies the two directions by $1/\sigma$: 0.5 and 100. Any noise in the weak direction is magnified a hundred times.

Ridge regularisation adds a small number $\alpha>0$ before inverting:

Where $\sigma_k$ is large, $\sigma_k/(\sigma_k^2+\alpha)$ is close to $1/\sigma_k$. Where $\sigma_k$ is small, it stays small instead of exploding.

Compare the bars. The strong direction is barely touched, 0.5 against 0.499. The weak one drops from 100 to under 1.

Worked example

1. Build it. $\mathbf{B}_2=(1,2)\,(1,1)^\top$ has $\sigma_1=\sqrt{10}$, $\mathbf{u}_1=(1,2)/\sqrt5$ and $\mathbf{v}_1=(1,1)/\sqrt2$, so $\mathbf{B}_2^+=\tfrac1{10}\begin{bmatrix}1&2\\1&2\end{bmatrix}$, and $\mathbf{B}_2\mathbf{B}_2^+\mathbf{B}_2=\mathbf{B}_2$.

2. Shortest answer. For $\mathbf{b}=(3,6)$: $(1.5,1.5)$, length 2.121. For $\mathbf{b}=(1,0)$: $(0.1,0.1)$, which reaches $(0.2,0.4)$.

3. Ridge with $\alpha=1$. $\mathbf{B}_2^\top\mathbf{B}_2+\mathbf{I}=\begin{bmatrix}6&5\\5&6\end{bmatrix}$, with inverse $\tfrac1{11}\begin{bmatrix}6&-5\\-5&6\end{bmatrix}$, and $\mathbf{B}_2^\top(1,0)=(1,1)$. So $\mathbf{x}_{\alpha=1}=\tfrac1{11}(1,1)$, which is $\tfrac{10}{11}$ of $\mathbf{x}^+=(0.1,0.1)$: the factor $\sigma^2/(\sigma^2+\alpha)=10/11$. As $\alpha$ shrinks to 0, $\mathbf{x}_\alpha$ tends to $\mathbf{x}^+$.

4. Full column rank. For the $3\times2$ matrix $\mathbf{B}=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}$, $\mathbf{B}^+=\tfrac13\begin{bmatrix}2&-1&1\\-1&2&1\end{bmatrix}$, and $\mathbf{B}^+(1,2,6)=(2,3)$: the least-squares answer of Projections.

Try these before you read the answers.

• $\mathbf{A}^+$ of an invertible $\mathbf{A}$? $\mathbf{A}^{-1}$.
• Is $\mathbf{B}_2^+\mathbf{B}_2=\mathbf{I}$? No: it projects onto the line of $(1,1)$.
• What does a larger $\alpha$ do to the answer’s length? It shrinks it, by $\sigma^2/(\sigma^2+\alpha)$ in each direction.
• $\mathbf{A}$ has singular values 3 and 0. The matching entries of $\boldsymbol{\Sigma}^+$? $1/3$ and 0.

Where you’ll meet this

Least-squares software. Library routines for least squares and the pseudo-inverse work through the SVD, so a fit with redundant or nearly redundant columns still returns a sensible answer, the shortest one.

Redundant sensors. Calibrating a set of sensors that measure overlapping things gives a system with dependent columns; the pseudo-inverse picks one consistent answer.

Rebuilding a signal from its spectrogram. Inverting the STFT finds the signal whose overlapping frames best match a set of edited frames: a least-squares inverse.

Statistics. Ridge regression fits a model with many inputs by the formula above, trading a little bias for much less noise.

Reference card