Database Reference
In-Depth Information
SU
T
a
0
T
V
T
a
akk
0
½
A
;
a
¼U
;
ð
8
:
15
Þ
0
T
akk
1
where a
⊥
:
¼
(
I UU
T
)
a
.
The proof is by a straightforward evaluation of the right-hand side of (
8.15
).
Without loss of generality, we shall henceforth assume that
a 6¼
0. The
simplest case obtains if
U
T
a ¼
0, that is,
a
lives in the orthogonal complement
of the range of
A
. Then, up to a permutation, (
8.15
) is already an SVD of [
A,a
]
and we are done. Now let us assume that
U
T
a 6¼
0. For the sake of simplicity,
we may safely neglect the case where
a
⊥
¼
0 since a slight and obvious
modification of the subsequent argumentation will do the trick. Under this
assumption, both of the matrices
,
V
a
akk
V
T
0
0
T
1
U
:¼
U
;
:¼
have orthogonal columns. Hence, if we are given a full-rank truncated SVD
SU
T
a
0
T
¼ U S V
T
S
:¼
akk
:¼ VV
have orthogonal columns. Thus, the
desired full-rank truncated SVD is given by
U
:¼ UU
and
V
then the matrices
¼U S V
T
½
A
;
a
and we are done. Therefore, it all comes down to computing a full-rank
truncated SVD of
S
. Unfortunately, the efficient computation of an SVD of
S
is left open in Brand's papers. We therefore outline the approach devised by
Paprotny [Pap09].
Fortunately, it turns out that the special structure of this matrix may be exploited
for efficient computation: we have
SS
T
0
SS
T
þ zz
T
,
¼
0
T
0
where
U
T
a
akk
z
:¼
:
Hence,
SS
T
is a rank-1 modification of a diagonal matrix. Again, the computation
of a spectral decomposition of matrices of this type is well understood in numerical
linear algebra. A sophisticated approach presented in [GE94] relies crucially on the
solution of a so-called secular equation. One of the most fundamental insights of
