Page 415 - Matrix Analysis & Applied Linear Algebra

5.12 Singular Value Decomposition 411
5.12 SINGULAR VALUE DECOMPOSITION

For an m × n matrix A of rank r, Example 5.11.2 shows how to build a URV
factorization
0 T
C r×r
T
A = URV = U V
0 0
m×n
in which C is triangular. The purpose of this section is to prove that it’s possible
to do even better by showing that C can be made to be diagonal.Tosee how,
let σ 1 = A 2 = C 2 (Exercise 5.6.9), and recall from the proof of (5.2.7) on
p. 281 that C 2 = Cx 2 for some vector x such that
2
T
T
T
(C C − λI)x =0, where x 2 =1 and λ = x C Cx = σ . (5.12.1)
1

Set y = Cx/ Cx 2 = Cx/σ 1 , and let R y = y | Y and R x = x | X be
elementary reflectors having y and x as their first columns, respectively—recall
T
T
Example 5.6.3. Reflectors are orthogonal matrices, so x X = 0 and Y y = 0,
and these together with (5.12.1) yield
T
T
T
x C CX λx X T T
T
y CX = = = 0 and Y Cx = σ 1 Y y = 0.
σ 1 σ 1
T
T
Coupling these facts with y Cx = y (σ 1 y)= σ 1 and R y = R T produces
y
T
y T T
y Cx y CX σ 1 0
R y CR x = C x | X = T T =
Y T Y Cx Y CX 0 C 2
with σ 1 ≥ C 2 (because σ 1 = C 2 = max{σ 1 , C 2 } by (5.2.12)). Repeat-
2
ing the process on C 2 yields reflectors S y , S x such that

σ 2 0
S y C 2 S x = , where σ 2 ≥ C 3 .
2
0 C 3
If P 2 and Q 2 are the orthogonal matrices
 
σ 1 0 0
1 0 1 0
P 2 = R y , Q 2 = R x , then P 2 CQ 2 =  0 σ 2 0 
0 S y 0 S x
0 0 C 3
in which σ 1 ≥ σ 2 ≥ C 3 . Continuing for r − 1 times produces orthogonal
2
matrices P r−1 and Q r−1 such that P r−1 CQ r−1 = diag (σ 1 ,σ 2 ,...,σ r )= D,
˜
˜ T
where σ 1 ≥ σ 2 ≥ ··· ≥ σ r . If U and V are the orthogonal matrices

˜
˜
˜ T
˜ T
T
U = P r−1 0 U and V = V Q r−1 0 , then U AV = D0 ,
0 I 0 I 0 0
57
and thus the singular value decomposition (SVD) is derived.
57
The SVD has been independently discovered and rediscovered several times. Those credited
with the early developments include Eugenio Beltrami (1835–1899) in 1873, M. E. Camille
Jordan (1838–1922) in 1875, James J. Sylvester (1814–1897) in 1889, L. Autonne in 1913, and
C. Eckart and G. Young in 1936.