The pseudoinverse

A scale reports three weighings of two objects. The first object alone weighs 1, the second alone weighs 1, and together they weigh 3. No pair of weights satisfies all three readings, because the first two say the total is 2 and the third says 3. The readings are not wrong in any obvious way; they are more numerous than the unknowns, and the system asks for one weight per object from three separate demands. An overdetermined system is one like this: more equations than unknowns, with no exact solution for most right-hand sides, the lists that sit to the right of the equals signs [S:21:235].

The compromise is the one from Section 8.4. Choose the two weights whose predictions come closest to the readings, measured by the residual sum of squares, and accept that no choice makes the cost zero. That choice always exists, and when the columns of the table are independent it is unique. The rule that maps readings to weights is a generalised inverse, written $A^{+}$ and called the pseudoinverse [S:21:239]. !The three weighings demand w1=1, w2=1 and w1+w2=3, and the three lines have no common point. Least squares returns (4/3,4/3) inside the triangle, with residuals 1/3, 1/3 and −1/3 and cost 1/3; the bolder (1,1) sits on a vertex, fits two readings exactly and costs three times as much. Status: re-simulated.

The pseudoinverse extends the ordinary inverse to tables that are not square. The inverse of a square table is the table that undoes it, returning the coefficient list from the predictions; it exists only when the columns are independent. For a table with independent columns the pseudoinverse is built from the normal equations.

The formula is a closed form: a recipe you can write down and evaluate directly, with no search and no iteration. It says that the pseudoinverse solves the least-squares problem in one step, since multiplying the readings by $A^{+}$ returns the best weights. When the table happens to be square and invertible, the pseudoinverse is the ordinary inverse, so the definition extends the old one rather than replacing it. The order of the two factors matters: $A^{\top }A$ is square and can be inverted, while $A^{\top }$ alone has the other shape, so the inverse must sit on the left of $A^{\top }$ and never on its right. Read the formula from the inside out: $A^{\top }\mathbf{b}$ takes the dot product of the readings with each column, giving one number per coefficient, and $(A^{\top }A{)}^{-1}$ then corrects those numbers for the overlap between the columns.

Worked example. The three readings give the table with rows (1, 0), (0, 1) and (1, 1), and the readings 1, 1 and 3. The normal equations have matrix entries 2, 1, 1 and 2, with right-hand side 4 and 4. With the weights written $w_1$ and $w_2$, the two equations are $2w_1+w_2=4$ and $w_1+2w_2=4$, whose solution is $w_1=4/3$ and $w_2=4/3$.

The predictions are 1.3333, 1.3333 and 2.6667, and the recorded values are 1, 1 and 3, so with the convention of Section 8.4 the residuals are −1/3, −1/3 and 1/3. The residual sum of squares is 1/3 = 0.3333. The exact compromise splits the missing weight evenly, which is what the symmetry of the readings demands.

Any answer that gave one object more weight would fit one of the single-object readings worse and the other one better, and the symmetric cost treats those two mistakes identically. The matrix of normal equations also shows how safe the answer is: it stretches one direction by 3 and the other by 1, so its condition number is 3 and the weights are stable in every digit shown. Two nearly equal columns would stretch one direction by almost nothing and send the weights swinging.

Now compare with a bolder choice. Setting both weights to 1 satisfies the first two readings exactly and misses the third by 1, for a residual sum of squares of 1. The least-squares answer misses all three slightly and scores 0.3333, which is three times smaller. Fitting some rows perfectly is not the goal, and a rule that chases the rows it can satisfy exactly will lose on the total.

When the columns are dependent, the minimising weights are not unique, and the pseudoinverse returns the shortest one. Treil shows that among all the minimisers there is exactly one of smallest norm, and the singular value construction produces it [S:25:195]. That construction writes the table as a product of two orthonormal bases and a diagonal list of stretches, and the Deepen carries it out. The convention is a choice rather than a theorem about the world, and it matters when two features carry the same information. A repeated column is the clearest case: the same total can be split between the two copies in infinitely many ways, and the shortest split gives each copy half.

Two costs come with it. The closed form inverts a matrix built from the data, so the squared condition number of Section 8.4 applies with full force [S:28:109]. The shortest-list convention is invisible in the output: you get one answer with no sign that a family of answers scored equally well.

Regularisation replaces the hard choice with a penalty, a charge added to the cost for large coefficients, and it is the usual repair. The price is a deliberate bias, an answer pulled toward smaller weights whether or not the data ask for it [S:28:88]. The next section asks when a small residual stops being evidence of a good model.

The formal statement. Write the reduced singular value decomposition of $A$ as $A=U\Sigma V^{\mathsf{T}}$, with ${\sigma }_1\ge \cdots \ge {\sigma }_r>0$ the nonzero singular values. The pseudoinverse is

$$A^{+}=V{\Sigma }^{-1}{U}^{\mathsf{T}},$$

where the inverse applies to each nonzero singular value and sends the rest to zero [S:25:195]. For any reading list $\mathbf{b}$, the list $\mathbf{c}=A^{+}\mathbf{b}$ is the least-squares solution of smallest norm.

The derivation. Expand the product in the two bases. For a reading $\mathbf{b}$, the construction returns $A^{+}\mathbf{b}={\sum }_{i=1}^r({\mathbf{u}}_i\cdot \mathbf{b}/{\sigma }_i){\mathbf{v}}_i$. Applying $A$ gives ${\sum }_i({\mathbf{u}}_i\cdot \mathbf{b}){\mathbf{u}}_i$, which is the orthogonal projection of $\mathbf{b}$ onto the span of the ${\mathbf{u}}_i$. That span is the column space of $A$, so the residual of $A^{+}\mathbf{b}$ is orthogonal to the column space. That is the normal-equation condition of Section 8.4, so the construction returns a least-squares solution [S:25:196].

For the norm claim, any other least-squares solution differs from $A^{+}\mathbf{b}$ by a list in the null space of $A$. The construction places $A^{+}\mathbf{b}$ in the span of the ${\mathbf{v}}_i$ with ${\sigma }_i>0$, which is the orthogonal complement of the null space. Adding a null-space list therefore adds a perpendicular component, and by Pythagoras the norm grows. So the shortest minimiser is unique, and the construction finds it.

The edge case. L1 wrote $A^{+}=(A^{\mathsf{T}}A{)}^{-1}{A}^{\mathsf{T}}$, which needs $A^{\mathsf{T}}A$ to be invertible. That fails when the columns are dependent. The singular value formula does not fail: it inverts only the nonzero singular values and discards the rest. A tiny singular value is the dangerous case, because inverting it turns a small amount of noise into a large coefficient. The formula is exact and the computed answer is not. A repeated column is the concrete version: the same total splits in infinitely many ways, the normal-equation inverse does not exist, and the construction still returns one answer.

What L1 hid. L1 called the shortest-list rule "a choice rather than a theorem". The construction makes the choice precise and shows it is not arbitrary. For $\lambda >0$ the ridge solution is $(A^{\mathsf{T}}A+\lambda I{)}^{-1}{A}^{\mathsf{T}}\mathbf{b}$, and in the underdetermined case the limit as $\lambda$ tends to zero is the minimum-norm solution [S:28:106]. The pseudoinverse is the endpoint of a family of penalised answers, not a separate convention. The simplification was safe because L1 used a table with independent columns, where the closed form and the construction agree exactly.

Where the analogy breaks. L1 said the pseudoinverse "extends the ordinary inverse". It does, but $A^{+}A$ is a projection, not the identity, whenever the columns are dependent. The ordinary inverse undoes the map. The pseudoinverse undoes only the part of the map that the data can see, and it reports nothing about the part it discarded.

Original sources. Treil constructs the Moore–Penrose inverse from the singular value decomposition, calls it the operator giving the least-squares solution, and lists the four conditions that define it in the literature [S:25:195]. Boyd derives the same object from the normal equations in the full-column-rank case and notes that $(A^{\mathsf{T}}A{)}^{-1}{A}^{\mathsf{T}}$ is the pseudo-inverse [S:21:239]. Treil's distinguished solution is the one of minimal norm among all the least-squares solutions [S:25:195].

An open question. The field has not settled when a minimum-norm answer is the right answer. The convention is a property of the construction, not of the world, and a different penalty gives a different shortest list. Ridge regression shrinks every coefficient toward zero, the pseudoinverse leaves the row-space part untouched, and both arise from the same family of penalised problems [S:28:88]. Evidence that would settle a given case: held-out error for the two conventions on the same data, with the failure mode of each measured and the coefficient lists printed beside the errors, rather than a preference stated in advance.

A frontier method. Gradient descent on an overparameterised least-squares problem converges to the minimum Euclidean-norm interpolating solution when it starts from zero [S:77:360]. That result gives the pseudoinverse a dynamical interpretation: the convention is what the optimiser selects among the many lists that fit. It is the hinge between the linear algebra of this chapter and the implicit-regularisation results used to explain modern networks.

What to read next. Read Treil's section 4.5 [S:25:195] for the singular value construction and the four conditions, Boyd's chapter 12 [S:21:235] for the full-rank case and its warnings, and Bach's chapter 12 [S:77:360] for the optimisation view. Then read Solomon's treatment of Tikhonov regularisation [S:28:88] for what happens when you replace the hard choice with a penalty, and the limit taken in [S:28:106] for how the two answers connect.