Linear AlgebraThe Singular Value Decomposition4 of 6
The Singular Value Decomposition · 4
The Pseudoinverse: The Best Effort Inverse
We want to solve Ax=b even when the matrix A has no inverse.
1
Why Inverses Break and the Two Rules for A+
The pseudoinverse A+ is the best-effort inverse of a matrix A: when Ax=b cannot be solved the normal way, A+ finds the shortest input vector x+ that gets the output Ax+ as close as possible to the target b.
Why Inverses Break and the Two Rules for A⁺
When A squashes space or has different input and output dimensions, A+ replaces A−1 by following one rule in the output space and one rule in the input space:
x+Ax+shortest inputin row spacex+=pseudoinverseA+bsuch that=closest point incolumn spaceb^and⊥null space
Moving the target b perpendicular to the column space does not change its orthogonal projection b^ or the dashed line of inputs that map to it, and the shortest input x+ always meets that solution line at a 90∘ angle inside the row space.
The shortest input stays on the row space for every output vector, and never changes when that output moves perpendicular to the column space.
2
Pseudoinverting Diagonal Matrices
To build a matrix that follows both rules, we start with the simplest case: finding the pseudoinverse Σ+ of a diagonal matrix Σ that only stretches or squashes along the standard axes.
Pseudoinverting Diagonal Matrices
AA+=[2000]=?
For any diagonal matrix Σ, transpose the matrix shape so outputs map back to inputs, invert every nonzero diagonal stretch σi→σi1, and leave every 0 as 0:
Σ=2000503×2⟶Σ+=[21005100]2×3
Text solution
Invert the nonzero stretch and keep the zeroFor A=[2000] and target b=[64], turn the horizontal stretch 2 into 21 and leave the squashed vertical 0 alone.
A=[2000]⟶A+=[21000]
Multiply A+b to find the shortest inputThe zero in the bottom-right entry zeroes out the unreachable 4 and puts a 0 in the null-space y-coordinate.
x+=A+b=[21000][64]=[30]
Multiply Ax+ to find the closest reachable outputMultiplying x+ by A lands on the orthogonal projection of b onto the x-axis.
b^=Ax+=[2000][30]=[60]
So x+=[30] is the shortest input vector that lands on b^=[60], the closest point on the x-axis to [64].
3
The SVD Pseudoinverse: A+=VΣ+UT
Now we want to find A+ for any matrix A that squashes space at an angle, by factoring A=UΣVT with the Singular Value Decomposition (SVD) and undoing each step.
The SVD Pseudoinverse: A⁺ = VΣ⁺Uᵀ
AA+=rotateUstretchΣrotateVT=?
Undoing the three steps of A=UΣVT in reverse order gives the general formula for the pseudoinverse:
A=UΣVT⟶A+=VΣ+UT
Text solution
Find the output directions U, input directions V, and stretches ΣFor A=[11−1−1] and b=[62], divide the column-space direction [11] by its length 2 to get u1, do the same for the row-space direction [1−1] to get v1 and for their perpendiculars to get u2 and v2, and use Av1=2u1 to find the stretches σ1=2 and σ2=0.
UΣV=21[11−11],=[2000],=21[1−111]
Pseudoinvert the diagonal matrix ΣInvert the nonzero singular value 2 and keep the zero on the diagonal.
Σ+=[21000]
Multiply VΣ+UT in reverse orderCombine the two 21 factors in front into 21 and multiply the three matrices to get A+.
Multiply A+b to get the best-effort inputMultiply A+ by the target vector b=[62].
x+=A+b=41[1−11−1][62]=41[8−8]=[2−2]
So x+=[2−2] is the shortest input (squared length 8) that maps to b^=Ax+=[44], the closest point on the column-space line y=x to [62].
Rotating the output space by UT lines the tilted column space up with the horizontal axis so the zero in Σ+ zeroes out the vertical gap, and V rotates the remaining horizontal vector straight into the tilted row space as x+.
The first rotation lines the tilted column space up with the horizontal axis so the middle step can zero out the vertical gap, and the last rotation turns what remains straight into the row space.
4
Shortcut for Tall Matrices with Independent Columns
Finding a full SVD takes work, so we want a direct shortcut when A is a tall matrix with independent columns.
Shortcut for Tall Matrices with Independent Columns
Because the gap vector b−Ax+ is perpendicular to every column of A, multiplying the gap by AT gives zero and lets us solve directly for x+:
Be careful not to confuse ATb with the projection b^: multiplying by AT takes dot products with the columns of A, which sends b into the smaller input space while ignoring the perpendicular gap (ATb=ATb^). Once you have x+=A+b, multiply by A on the left to get the projection b^=Ax+ back in the output space.
5
Shortcut for Wide Matrices with Independent Rows
Now take the opposite case: a direct shortcut for a wide matrix with independent rows, where Ax=b has many solutions and we want the shortest one.
Shortcut for Wide Matrices with Independent Rows
[101101]x1x2x3x+=[33]=?
To avoid any extra length in the null space, x+ must be a combination of the rows of A, written as x+=ATy for some weight vector y:
Multiply A+b to find the shortest solutionMultiply A+ by the target vector b=[33].
x+=A+b=3121−1−112[33]=31363=121
So x+=121 solves the system with squared length 12+22+12=6, shorter than other solutions like 030 (squared length 9) because it has no part in the null space.
Every point x along the solution line in 3D input space maps to the exact same output b, and moving away from the 90∘ row-space intersection x+ only adds null-space length to ∥x∥2.
Every point on the line of solutions gives the exact same output, and moving away from the row space along the line only adds length from the null space.
6
AA+ and A+A as Projection Matrices
Finally, we want to know what happens when we multiply A and A+ together. Because any part of the target off the column space can never be reached, and any part of the input squashed into the null space is gone for good, AA+ and A+A are not always the identity matrix I. Instead, they are orthogonal projection matrices.
AA⁺ and A⁺A as Projection Matrices
Multiplying in each order projects a vector onto the subspace that isn't squashed:
Writing both products using the SVD shows that ΣΣ+ and Σ+Σ are diagonal matrices with 1s along the directions that survive and 0s along the unreachable or squashed directions:
AA+A+A=U(ΣΣ+)UT,=V(Σ+Σ)VT
Because A squashes xnull to zero, the round trip A+Ax keeps only the row-space part xrow, and gives back x only if x started in the row space.
A round trip forward and back through the pseudoinverse drops the null-space part of any input and lands on its shadow in the row space.
Key concepts
Whenever you need to solve Ax=b, first check whether you need a pseudoinverse at all: if A is a square matrix with independent columns (det(A)=0, such as A=[2003]), every output can be reached from a single input and the regular inverse x=A−1b=[210031]b solves it directly. When A is rectangular or has determinant 0,x+=A+b gives the shortest input in the row space that lands on the closest point b^=Ax+ in the column space.
Pick the formula for A+ by checking which case you have:
Key concept
If the matrix is already a diagonal stretch Σ, transpose the matrix shape, invert the nonzero entries (σi→σi1), and leave zeros as 0: for Σ=[2000],Σ+=[21000].
Key concept
If A is tall with independent columns (such as a 3×2 matrix whose columns are not multiples of each other), ATA is the small invertible 2×2 square matrix, so use A+=(ATA)−1AT.
Key concept
If A is wide with independent rows (such as a 2×3 matrix whose rows are not multiples of each other), AAT is the small invertible 2×2 square matrix, so use A+=AT(AAT)−1.
Key concept
If A has dependent columns and dependent rows (such as A=[11−1−1], where det(ATA)=0 and det(AAT)=0), neither shortcut matrix is invertible, so factor A=UΣVT and undo the steps in reverse with A+=VΣ+UT.
Once you have A+, multiplying A and A+ gives orthogonal projections: AA+ has A on the left and projects any output vector b onto the column space (b^=AA+b), while A+A has A+ on the left and projects any input vector x onto the row space (xrow=A+Ax, with null-space part xnull=x−xrow).
7
Practice
1
Given the 3×2 diagonal stretch matrix Σ=400000 and the target vector b=83−5, find the pseudoinverse Σ+, the best-effort input x+=Σ+b, and the closest reachable output b^=Σx+.
Σ maps 2 inputs to 3 outputs. What dimensions must Σ+ have to map 3 outputs back to 2 inputs, and what happens to the 4 and the 0s?
Transpose the 3×2 shape into 2×3, invert the nonzero stretch 4→41, and leave every 0 as 0 (do not leave Σ+ as a 3×2 matrix, which cannot multiply the 3×1 target b):
Σ+=[4100000]
Multiply Σ+b to find x+, then multiply Σx+ to find b^ (do not stop at x+ and write 200 for b^, since multiplying by Σ stretches the first coordinate back by 4):
The tall matrix A=110111 has independent columns. Find its pseudoinverse A+=(ATA)−1AT, then find the best-effort input x+ and the column-space projection b^=Ax+ for the unreachable target b=261.
Watch the minus signs on the off-diagonal entries when inverting ATA, since leaving them positive gives 21[3222] and the wrong input [2117].
Multiply ATA first to get a 2×2 matrix you can invert; once you have x+=A+b, which matrix sends x+ back into the 3D output space?
Compute ATA and invert it using det(ATA)=6−4=2 (watch the minus signs on the off-diagonal entries when inverting ATA, since leaving them positive gives 21[3222] and the wrong input [2117]):
The wide system [102121]x1x2x3=[52] has independent rows and infinitely many solutions. Compute A+=AT(AAT)−1 and find the shortest input vector x+ that solves the system.
Do not forget to divide by det(AAT)=18−16=2, or every entry will be doubled and give x+=222, which maps to [104] instead of [52].
Check the dimensions and determinant of AAT before inverting, and keep AT on the left when you multiply AT(AAT)−1.
Multiply AAT and invert the resulting 2×2 matrix (do not forget to divide by det(AAT)=18−16=2, or every entry will be doubled and give x+=222, which maps to [104] instead of [52]):
For A=[12−2−4] and b=[155], neither ATA nor AAT is invertible. Find the SVD A=UΣVT, use it to compute A+=VΣ+UT, and find the best-effort solution x+=A+b.
Both columns are multiples of [12] and both rows are multiples of [1−2]. Divide those vectors by their length to get the unit vectors u1 and v1, then multiply Av1 to find the stretch σ1.
Divide the column-space direction [12] and row-space direction [1−2] by their length 5 (forgetting the 51 length factors leaves out a factor of 51 in A+ and gives [5−10]), and use Av1=5u1 to get σ1=5:
UΣV=51[12−21],=[5000],=51[1−221]
Invert the nonzero stretch 5→51 in Σ+ and multiply VΣ+UT in reverse order (multiplying in forward order UΣ+VT flips the signs of the off-diagonal entries and gives [5152] in the column space instead of the row space):
For A=[3040], find A+, compute the column-space projection matrix AA+ and the row-space projection matrix A+A, and use A+A to split the input x=[50] into its row-space part xrow and null-space part xnull.
Row 1 points along the row space with length 32+42=5 while row 2 is zero; once you have A+, check which order (AA+ vs A+A) lands in the input's row space.
With u1=[10],v1=51[34], and σ1=5, build A+ and compute both projection matrices:
Multiply x by the row-space projection A+A to find xrow, then subtract from x to find xnull (do not multiply x by AA+=[1000], which projects onto the output column space and wrongly gives xrow=[50] and xnull=[00]):