Principles of Mathematics in Operations Research

3.2 Projections and Least Squares Approximations 43

=> x =

0"

L

a

0

= A*b =

"0 0 0

OiO

ooi

0 0 0

Thus, A* =

"0 0

0 0

.0 0

0"

0

0.

3.2.4 Singular Value Decomposition

Definition 3.2.18 A 6 Rmxn, A — Q\EQ% is known as singular value

decomposition, where Qx G Rmxm orthogonal, Q 2 £ E""*"^1 orthogonal, and

E has a special diagonal form

E =

with the nonzero diagonal entries called singular values of A.

Proposition 3.2.19 A* = Q 2 E^Ql where £+

Proof. ||Ac - 6|| = \\Qi2QZx - b\\ = \\EQ$x - Qfb\\.

This is multiplied by Qf y = Q\x = Q 2 ~^1 x with \\y\\ = ||a

min \\Ey - Q\b\\ -» y = E^Qjb.

^x = Q 2 y = Q 2 E^Qjb => A^ = Q 2 E^Qj O

Remark 3.2.20 A typical approach to the computation of the singular value
decomposition is as follows. If the matrix has more rows than columns, a QR
decomposition is first performed. The factor R is then reduced to a bidiagonal
matrix. The desired singular values and vectors are then found by performing
a bidiagonal QR iteration (see Remarks 6.2.3 and 6.2.8).