13.17. LEAST SQUARES AND SINGULAR VALUE DECOMPOSITION 377
13.17 Least Squares And Singular Value DecompositionThe 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 12.4.1 shows that there is a solution to this problem which can be foundby solving the system A∗Ax= A∗y. Each x which solves this system solves the minimiza-tion problem as was shown in the lemma just mentioned. Now consider this equation forthe solutions of the minimization problem in terms of the singular value decomposition.
A∗︷ ︸︸ ︷V
(σ 00 0
)U∗
A︷ ︸︸ ︷U
(σ 00 0
)V ∗x=
A∗︷ ︸︸ ︷V
(σ 00 0
)U∗y.
Therefore, this yields the following upon using block multiplication and multiplying on theleft by V ∗. (
σ2 00 0
)V ∗ x=
(σ 00 0
)U∗y. (13.33)
One solution to this equation which is very easy to spot is
x=V
(σ−1 0
0 0
)U∗y. (13.34)
13.18 The Moore Penrose InverseThe particular solution of the least squares problem given in 13.34 is important enough thatit motivates the following definition.
Definition 13.18.1 Let A be an m×n matrix. Then the Moore Penrose inverse of A, denotedby A+ is defined as
A+ ≡V
(σ−1 0
0 0
)U∗.
Here
U∗AV =
(σ 00 0
)as above.
Thus A+y is a solution to find x which minimizes |Ax−y| . In fact, one can say moreabout this. In the following picture My denotes the set of least squares solutions x suchthat A∗Ax= A∗y.