Database Reference
In-Depth Information
We obtain for a rank-2 approximation
0
@
1
A
,
:
10
3
X ¼
:
0
:
0
2
7
:
0
:
0
1
7
0
1
T
0
:
02
0
:
1
@
A
11
49 0
06
:
0
:
24
0
:
96
0
:
23
2
:
76
9
:
65
5
:
17
Y ¼
¼
:
88
0
:
84
0
:
02
0
:
69
6
:
61
:
65
0
:
14
0
:
45
0
:
02
and
0
1
0
:
02
0
:
78
10
:
14
5
:
13
@
A
A
k
¼ XY ¼
0
:
53
5
:
17
0
:
78
1
:
13
0
:
51
4
:
9
0
:
19
0
:
62
already provides a fairly good approximation to
A
.
■
This terrific result tells us that the computation of a solution of (
8.8
) may be
reduced to computing a truncated singular value decomposition of
A
. It should be
clear from the above derivation that this problem, in turn, may be essentially solved
by computing a truncated spectral decomposition of the Gram matrix
A
T
A
. Calcu-
lation of spectral decompositions of symmetric and positive definite matrices,
fortunately, is a well-understood domain of numerical linear algebra. In particular,
this problem may be solved within polynomially bounded time in terms of dimen-
sionality and desired accuracy.
The bad news is that the complexity of state-of-the-art solvers increases with the
number of columns of
A
. Hence, these methods are not suitable for realtime
computation.
8.3.2
Incremental Computation of the Singular
Value Decomposition
In what follows, we shall present an approach to incremental computation of the
SVD. In a nutshell, we shall address the following question: given a matrix
A
and a
vector
a
, how can we express the SVD of [
A,a
] in terms of that of
A
? The
subsequent lemma, which summarizes the reasoning of Brand [Bra06, Bra03,
Bra02, GE94], is crucial.
m
.
Furthermore, let A ¼ U
r
S
r
V
r
,
where r
rank A, be a full-rank truncated SVD
.
Let U
:
¼ U
r
,
S
:
¼ S
r
, and V
:
¼ V
r
. Then we
have
mn
Lemma 8.1
Let A
,
a
∈ R
∈R
