Page 51 - Compact Numerical Methods For Computers
P. 51
Singular-value decomposition, and use in least-squares problems 41
dominant principal components can be computed. Furthermore, at this stage in
T
the calculation U b should already have been computed and saved, so that only a
simple matrix-vector multiplication is involved in finding each of the solutions.
Another way to look at this is to consider the least-squares problem
Bw b (3.38)
where B is the matrix having orthogonal columns and is given in equations (3.1)
and (3.6). Thus the normal equations corresponding to (3.38) are
2
T
T
B Bw = S w = B b. (3.39)
2
But S is diagonal so that the solutions are easily obtained as
- 2 T
w = S B b (3.40)
and substitution of (3.6) gives
- 1 T
w = S U b. (3.41)
Should the problem be singular, then
+ T
w = S U b. (3.42)
can be used. Now note that because
BV T = A (3.43)
from (3.1), the solution w allows x to be computed via
x = Vw. (3.44)
The coefficients w are important as the solution of the least-squares problem in
terms of the orthogonal combinations of the original variables called the principal
components. The normalised components are contained in U. It is easy to
rearrange the residual sum of squares so that
T T T T T T
r r = (b – Ax) (b – Ax) = (b – Bw) (b – Bw) = b b – b Bw (3.45)
by virtue of the normal equations (3.39). However, substituting (3.37) in (3.42)
and noting the ordering of S, it is obvious that if
S k+1,k+1 < q (3.46)
is the first singular value less than or equal to the tolerance, then
w = 0 for i > k. (3.47)
i
The components corresponding to small singular values are thus dropped from the
solution. But it is these components which are the least accurately determined
since they arise as differences. Furthermore, from (3.6) and (3.45)
T T T + T
r r = b b – b USS U b
(3.48)
where the limit of the sum in (3.48) is k, the number of principal components
which are included. Thus inclusion of another component cannot increase the