Page 45 - Compact Numerical Methods For Computers

Singular-value decomposition, and use in least-squares problems 35
specified tolerance. This has a side effect of speeding the calculations significantly
when rank deficient matrices are encountered.

3.4. A FINE POINT
Equations (3.15) and (3.19) cause the algorithm just described obviously to
proceed towards both an orthogonalisation and an ordering of the columns of the
(z)
resulting matrix A . However the rotations must be arranged in some sequence
to carry this task to completion. Furthermore, it remains to be shown that some
sequences of rotations will not place the columns in disorder again. For suppose
a is orthogonal to all other columns and larger than any of them individually. A
1
sequential arrangement of the rotations to operate first on columns (1, 2), then
(1, 3), (1, 4), . . . , (1, n), followed by (2, 3), . . . , (2, n), (3, 4), . . . , ((n – 1), n) will
be called a cycle or sweep. Such a sweep applied to the matrix described can easily
yield a new a for which
2
(3.29)
if, for instance, the original matrix has a = a and the norm of these vectors is
3
2
-½
greater than 2 times the norm of a . Another sweep of rotations will put
1
things right in this case by exchanging a 1 and a . However, once two columns
2
have achieved a separation related in a certain way to the non-orthogonality
measure (3.17), it can be shown that no subsequent rotation can exchange them.
Suppose that the algorithm has proceeded so far that the non-orthogonality
measure Z satisfies the inequality
2
Z < t (3.30)
where t is some positive tolerance. Then, for any subsequent rotation the
parameter p, equation (3.21), must obey
2 2
p < t . (3.31)
Suppose that all adjacent columns are separated in size so that
(3.32)
Then a rotation which changes a k (but not a ) cannot change the ordering of
k-1
the two columns. If x = a , then straightforward use of equations (3.23) and (3.24)
k
or (3.25) and (3.26) gives
T
T
X X – x x = (v – q)/2 > 0. (3.33)
Using (3.31) and (3.22) in (3.33) gives
(3.34)
Thus, once columns become sufficiently separated by size and the non-
orthogonality sufficiently diminished, the column ordering is stable. When some
columns are equal in norm but orthogonal, the above theorem can be applied to
columns separated by size.
The general question of convergence in the case of equal singular values has been