The pseudoinverse and the condition number
Slide 5 used the SVD to read data. Now we use it to undo a matrix. Lesson 3 said a singular or rectangular matrix has no inverse, and that is true: some information is lost for good. Think of the shadow of a stick on a wall. From the shadow you can tell how long the stick is from side to side, but not how far it points toward you. That part is gone. The pseudoinverse A⁺ does the best possible undo: it reverses every stretch that can be reversed, and sets the lost directions to zero. The same SVD also gives the condition number σ₁/σₙ (σₙ is the smallest singular value), which warns when a problem is so close to losing a direction that small errors blow up.
Lesson 8 · slide 6Pseudoinverse- Σ⁺ has the transposed shape of Σ (n by m when A is m by n). Its diagonal holds 1/σ for each nonzero σ; everything else is zero.
- A⁺ = VΣ⁺Uᵀ = (1/σ₁)v₁u₁ᵀ + … + (1/σᵣ)vᵣuᵣᵀ, using the nonzero σ's only. If A is invertible, A⁺ = A⁻¹.
- x⁺ = A⁺b is a least squares solution (lesson 5). When many x are equally good, A⁺ picks the shortest.
- The condition number σ₁/σₙ (σₙ is the smallest singular value) says how much errors in b can be amplified in x. It is infinite when σₙ = 0.
The best possible undo
A = UΣVᵀ is turn, stretch, turn. To undo it, go backwards: turn back with Uᵀ, undo each stretch by dividing by σ, turn back with V. Turns can always be undone (Uᵀ undoes U because UᵀU = I). A stretch by σ can be undone by 1/σ, unless σ = 0. A direction squashed to zero can't be brought back, so A⁺ leaves it at zero.
Written as pieces, like slide 3, the undo is a sum over the nonzero σ's only:
If A is invertible (square, no zero σ), then Σ⁺ = Σ⁻¹ and A⁺ = A⁻¹. A small example: A = 3000 has σ₁ = 3, σ₂ = 0, so A⁺ = 1/3000: the x-stretch is undone, the squashed y-direction stays at zero.
A worked example: two equations that disagree
The best compromise is x + y = 3 (the average of 2 and 4: it makes the two errors equal and as small as possible, which is what least squares from lesson 5 gives). But x + y = 3 is still a whole line of answers, like 30 or 12. Which one does A⁺ pick? The shortest one. Take any answer, such as 30, and project it onto the line through v₁ (lesson 5). The part you remove points along v₂, the direction A can't see, so Ax doesn't change:
Why the shortest? Every best answer is p plus some multiple of v₂, and p ⟂ v₂, so by Pythagoras its squared length is ‖p‖² plus something positive. Only p itself has nothing added.
The condition number
If σₙ is tiny compared with σ₁, A almost squashes a direction. Solving Ax = b divides by that tiny σₙ, so small errors in b blow up. The ratio σ₁/σₙ is the condition number. If σₙ = 0, like the A = 1111 above with σ₂ = 0, the condition number is infinite: that direction is lost completely. We compare errors by their relative size: the length of the error divided by the length of the vector. Start with a clear case:
A nearly singular matrix is much worse:
Keep reading with the full course
Finish lesson 8 and you will be able to: compress an image and keep only what matters.
Still locked here:
- The rest of this explanation
- 4 more examples with step-by-step solutions
- Five extra members-only problems with worked solutions
$20 once, lifetime access. Lessons 1 to 3 stay free.
Examples
Example 1 · An invertible matrix
A = 2004: A⁺ = ½00¼ = A⁻¹. Condition number 4/2 = 2: very safe.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.