12.11. LEAST SQUARES AND SINGULAR VALUE DECOMPOSITION 317
form
(σ′ 0
0 0
). For example, 3 0 0 0
0 2 0 0
0 0 1 0
is best approximated by the rank 2 matrix 3 0 0 0
0 2 0 0
0 0 0 0
Now suppose A is an m× n matrix. Let U, V be unitary and of the right size such that
U∗AV =
(σr×r 0
0 0
)Then suppose B approximates A as well as possible in the Frobenius norm. Then you wouldwant
∥A−B∥ = ∥U∗AV − U∗BV ∥ =
∥∥∥∥∥(σr×r 0
0 0
)− U∗BV
∥∥∥∥∥to be as small as possible. Therefore, from the above discussion, you should have
U∗BV =
(σ′ 0
0 0
), B = U
(σ′ 0
0 0
)V ∗
whereas
A = U
(σr×r 0
0 0
)V ∗
12.11 Least Squares and Singular Value Decomposi-tion
The singular value decomposition also has a very interesting connection to the problem ofleast squares solutions. Recall that it was desired to find x such that |Ax− y| is as small aspossible. Lemma 11.5.1 shows that there is a solution to this problem which can be found bysolving the system A∗Ax = A∗y. Each x which solves this system solves the minimizationproblem as was shown in the lemma just mentioned. Now consider this equation for thesolutions of the minimization problem in terms of the singular value decomposition.
A∗︷ ︸︸ ︷V
(σ 0
0 0
)U∗
A︷ ︸︸ ︷U
(σ 0
0 0
)V ∗x =
A∗︷ ︸︸ ︷V
(σ 0
0 0
)U∗y.
Therefore, this yields the following upon using block multiplication and multiplying on theleft by V ∗. (
σ2 0
0 0
)V ∗x =
(σ 0
0 0
)U∗y. (12.17)
One solution to this equation which is very easy to spot is
x = V
(σ−1 0
0 0
)U∗y. (12.18)