Page 43 - Compact Numerical Methods For Computers

Singular-value decomposition, and use in least-squares problems 33
a product of simpler matrices

(3.10)

where z is some index not necessarily related to the dimensions m and n of A, the
matrix being decomposed. The matrices used in this product will be plane
(k)
rotations. If V is a rotation of angle f in the ij plane, then all elements of V ( k )
will be the same as those in a unit matrix of order n except for

(3.11)

Thus V (k) affects only two columns of any matrix it multiplies from the right.
These columns will be labelled x and y. Consider the effect of a single rotation
involving these two columns

(3.12)

Thus we have
X = x cos f + y sin f
Y = –x sin f + y cos f. (3.13)

If the resulting vectors X and Y are to be orthogonal, then
T
T
2
2
T
T
X Y = 0 = –(x x – y y) sinf cosf + x y(cos f – sin f ). (3.14)
There is a variety of choices for the angle f, or more correctly for the sine and
cosine of this angle, which satisfy (3.14). Some of these are mentioned by
Hestenes (1958), Chartres (1962) and Nash (1975). However, it is convenient if
the rotation can order the columns of the orthogonalised matrix B by length, so
that the singular values are in decreasing order of size and those which are zero
(or infinitesimal) are found in the lower right-hand corner of the matrix S as in
equation (3.8). Therefore, a further condition on the rotation is that
T T
X X – x x > 0. (3.15)
For convenience, the columns of the product matrix

(3.16)

will be donated a , i = 1, 2, . . . , n. The progress of the orthogonalisation is then
i
observable if a measure Z of the non-orthogonality is defined

(3.17)

Since two columns orthogonalised in one rotation may be made non-orthogonal in
subsequent rotations, it is essential that this measure be reduced at each rotation.