How does the Moore-Penrose pseudoinverse solve a rank-deficient least-squares problem?

## The problem Least squares asks for x minimizing `||A x - b||_2`. When the columns of A are linearly independent there is exactly one minimizer. When A is **rank deficient**, meaning its rank r is smaller than its number of columns n, the minimizer is not unique: if x is a minimizer and z satisfies `A z = 0`, then `A(x + z) = A x`, so `x + z` gives the identical residual. The whole set of minimizers is a shifted copy of the null space of A, which has dimension n - r. Rank deficiency does not make least squares unsolvable; it makes it under-determined, and you must state which of the infinitely many answers you want. ## Building the pseudoinverse Take `A = U S V^T`. Define `S^+` as the n-by-m matrix obtained by transposing the shape of S and replacing each nonzero singular value `sigma_i` with its reciprocal `1 / sigma_i`, while every zero entry stays zero. Then `A^+ = V S^+ U^T` The key detail is that zeros are **not** inverted. There is no reciprocal of zero, and refusing to invent one is precisely what lets the construction work for singular and rectangular matrices. This matrix is the unique one satisfying the four **Moore-Penrose conditions**: `A A^+ A = A`, `A^+ A A^+ = A^+`, and both `A A^+` and `A^+ A` symmetric. When A is square and invertible, `A^+ = A^{-1}`, so it genuinely generalizes the inverse. ## What x = A^+ b gives you Two properties together: 1. **It is a least-squares solution.** `A A^+` is the orthogonal projector onto the column space of A, so `A x = A A^+ b` is the projection of b onto the reachable set, the closest point to b that A can produce. The residual `b - A A^+ b` is orthogonal to every column of A, which is the geometric form of the normal equations. 2. **It is the minimum-norm one.** `A^+ b` lies entirely in the row space of A, the orthogonal complement of the null space, so it has zero null-space component. Any other minimizer is `A^+ b + z` for some nonzero z in the null space, and because the two parts are orthogonal, `||A^+ b + z||^2 = ||A^+ b||^2 + ||z||^2 > ||A^+ b||^2`. So the pseudoinverse answer is strictly the shortest. Choosing the shortest solution is a **decision**, not a mathematical necessity. It is a defensible default: it refuses to put weight on directions the data cannot resolve. ## The numerical part In practice no computed singular value is exactly zero; a truly rank-deficient matrix produces values around the rounding-error level instead. Because A^+ scales the component of b along `u_i` by `1 / sigma_i`, a singular value near the noise floor is amplified enormously and the resulting x is dominated by whatever noise is in b along that direction. The standard remedy is a **tolerance**: treat any `sigma_i` below, say, `max(m, n) * eps * sigma_1` as zero and drop that direction entirely. This is a truncated pseudoinverse. It introduces a small bias in exchange for a large reduction in variance, and it is what makes the pseudoinverse usable on near-rank-deficient data where singular values are small but not zero. Setting the cutoff is a judgment call. Too tight and you keep noise-dominated directions; too loose and you discard real signal. Looking at the actual gap in the spectrum, if there is one, is more informative than any default. ## Relation to full-rank least squares When A has full column rank, every singular value is positive, the null space is trivial, and the minimizer is unique; `A^+ b` returns exactly the ordinary least-squares answer, and the minimum-norm property says nothing extra. Everything distinctive about the pseudoinverse shows up only when rank is deficient or nearly so. ## Common mistakes Saying A^+ equals A inverse for any square matrix (false as soon as A is singular); inverting the zero entries of S; claiming the least-squares solution is always unique; and inverting a tiny singular value without noticing that it multiplies the noise in b by an enormous factor.