Page 425 - Matrix Analysis & Applied Linear Algebra

5.12 Singular Value Decomposition 421

It’s proven on p. 435 that 9 q = P R(A) q is the vector in R (A) (the document
space) that is closest to q, so using 9 q in place of q has the effect of using the
best approximation to q that is a linear combination of the document vectors
T
T
d i . Since 9 q A = q A and 9 q ≤ q , it follows that cos θ j ≥ cos θ j , so
9
2 2
more documents are deemed relevant when the projected query is used. Just as
in the unprojected query matching strategy, the noise is filtered out by replacing
k T
A in (5.12.14) with a truncated SVD A k = σ i u i v . The result is
i=1 i
T
q U k s j
9
cos φ j =
U q s j

T
k 2 2
and, just as in (5.12.13), cos φ j is easily and quickly computed for each new
9
query q because U k and s j need only be computed once.
The next example shows why singular values are the primary mechanism
for numerically determining the rank of a matrix.
Example 5.12.5
m×n
Perturbations and Numerical Rank. For A ∈ with p = min{m, n},
let {σ 1 ,σ 2 ,...,σ p } and {β 1 ,β 2 ,...,β p } be all singular values (nonzero as well
as any zero ones) for A and A + E, respectively.
Problem: Prove that

|σ k − β k |≤ E 2 for each k =1, 2,...,p. (5.12.15)

Solution: If the SVD for A given in (5.12.2) is written in the form
p k−1
T T
A = σ i u i v , and if we set A k−1 = σ i u i v ,
i i
i=1 i=1
then
σ k = A − A k−1 = A + E − A k−1 − E
2 2
≥ A + E − A k−1 − E (recall (5.1.6) on p. 273)
2 2
≥ β k − E by (5.12.10).
2
Couple this with the observation that
σ k = min A − B 2 = min A + E − B − E 2
rank(B)=k−1 rank(B)=k−1

≤ min A + E − B 2 + E 2 = β k + E 2
rank(B)=k−1
to conclude that |σ k − β k |≤ E 2 .