Page 427 - Matrix Analysis & Applied Linear Algebra

5.12 Singular Value Decomposition 423

Moore–Penrose Pseudoinverse

• In terms of URV factors, the Moore–Penrose pseudoinverse of
−1
0 C 0
C r×r T † T
A m×n = U V is A n×m = V U . (5.12.16)
0 0 0 0
†
• When Ax = b is consistent, x = A b is the solution (5.12.17)
of minimal euclidean norm.
†
• When Ax = b is inconsistent, x = A b is the least (5.12.18)
squares solution of minimal euclidean norm.
• When an SVD is used, C = D = diag (σ 1 ,...,σ r ), so

−1 r T r T
D 0 T v i u i u b
i
†
A = V U = and A b = v i .
†
0 0 σ i σ i
i=1 i=1
Proof. To prove (5.12.17), suppose Ax 0 = b, and replace A by AA A to
†
write b = Ax 0 = AA Ax 0 = AA b. Thus A b solves Ax = b when it is
†
†
†
†
consistent. To see that A b is the solution of minimal norm, observe that the
general solution is A b+N (A)(a particular solution plus the general solution of
†
the homogeneous equation), so every solution has the form z = A b+n, where
†
T
n ∈ N (A). It’s not difficult to see that A b ∈ R A † = R A (Exercise
†
5.12.16), so A b ⊥ n. Therefore, by the Pythagorean theorem (Exercise 5.4.14),
†
2

2

2 2

2
†
z = A b + n
= A b + n ≥ A b .

†
†
2 2 2 2 2
†
Equality is possible if and only if n = 0, so A b is the unique minimum
norm solution. When Ax = b is inconsistent, the least squares solutions are the
T
T
solutions of the normal equations A Ax = A b, and it’s straightforward to
†
†
verify that A b is one such solution (Exercise 5.12.16(c)). To prove that A b
is the least squares solution of minimal norm, apply the same argument used in
the consistent case to the normal equations.
Caution! Generalized inverses are useful in formulating theoretical statements
such as those above, but, just as in the case of the ordinary inverse, generalized
inverses are not practical computational tools. In addition to being computation-
ally inefficient, serious numerical problems result from the fact that A † need