13.7. MOORE PENROSE INVERSE∗ 323

13.7 Moore Penrose Inverse∗

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 13.3.3 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.15)

One solution to this equation which is very easy to spot is

x =V

(σ−1 0

0 0

)U∗y. (13.16)

This special x is denoted by A+y. The matrix V

(σ−1 0

0 0

)U∗ is denoted by A+. Thus

x just defined is a solution to the least squares problem of finding the x such that Ax isas close as possible to y. Suppose now that z is some other solution to this least squaresproblem. Thus from the above,(

σ2 00 0

)V ∗z =

(σ 00 0

)U∗y

and so, multiplying both sides by

(σ−2 0

0 0

),

(Ir×r 0

0 0

)V ∗z =

(σ−1 0

0 0

)U∗y

To make V ∗z as small as possible, you would have only the first r entries of V ∗z be nonzerosince the later ones will be zeroed out anyway so they are unnecessary. Hence

V ∗z =

(σ−1 0

0 0

)U∗y

and consequently

z =V

(σ−1 0

0 0

)U∗y≡ A+y

However, minimizing |V ∗z| is the same as minimizing |z| because V is unitary. Hence A+yis the solution to the least squares problem which has smallest norm.