Spectral Perturbation Bounds for Positive Definite Matrices.
Let H and H positive definite matrices. It was shown by Barlow and Demmel and Demmel and Veselic that if one takes a componentwise approach one can prove much stronger bounds on $\lambda_i(H)/\lambda_i(H and the components of the eigenvectors of H and H than by using the standard normwise perturbation theory. Here a unified approach is presented that improves on the results of Barlow, Demmel, and Veselic. It is also shown that the growth factor associated with the error bound on the components of the eigenvectors computed by Jacobi's method grows linearly (rather than exponentially) with the number of Jacobi iterations required for convergence.
Introduction
. If the positive definite matrix H can be written as
where D is diagonal and A is much better conditioned than H then the eigenvalues
and eigenvectors of H are determined to a high relative accuracy if the entries of the
matrix H are determined to a high relative accuracy. This was shown by Demmel and
Veseli'c [2], building on work of Barlow and Demmel [1]. In this paper we strengthen
some of the perturbation bounds in [2], and present a unified approach to proving
these results. We also show that, just as conjectured in [2], the growth factor that
arises in the bound on the accuracy of the components of the eigenvectors computed
by Jacobi's method is linear rather than exponential.
We now give an outline of the paper and the main ideas in it and then define
the notation. In Section 2 we quickly reprove some of the eigenvalue and eigenvector
perturbation bounds from [2] in a perhaps more unified way and derive bounds on
the sensitivity of the eigenvalues to perturbations in any given entry of the matrix.
The main idea in this section is that the analysis is reduced to standard perturbation
theory if one can express additive perturbations as multiplicative perturbations. In
this respect our approach is similar to that of Eisenstat and Ipsen in [4], except
that they assume a multiplicative perturbation and then go on to derive bounds,
whereas we assume an additive perturbation, which we rewrite as a multiplicative
perturbation, before performing the analysis. Our results are the same as those in [4]
for eigenvalues, but not for eigenvectors. We briefly compare our approach to relative
perturbation bounds with those in [1, 2, 4] in Section 2.1. We also show that the
relative gap associated with an eigenvalue is a very good measure of the distance (in
the scaled norm) to the nearest matrix with a repeated eigenvalue.
In Section 3 we consider the components of the eigenvectors of a graded positive
definite matrix 1 . The key idea here is that if H is a graded positive definite matrix
and U is orthogonal such that H then U has a "graded"
Department of Mathematics, College of William & Mary, Williamsburg, VA 23187. e-mail:
na.mathias@na-net.ornl.gov. This research was supported in part by National Science Foundation
grant DMS-9201586 and much of it was done while the author was visiting the Institute for Mathematics
and its Applications at the University of Minnesota.
We say that the positive definite matrix H is graded if diagonal and A
is much better conditioned than H.
roy mathias
structure related to that of H and H 1 . 2 This fact can be systematically applied to
obtain component-wise perturbation bounds for the eigenvectors of "graded" positive
definite matrices and component-wise bounds on the accuracy of the eigenvectors
computed by Jacobi's method. The fact that the matrix of eigenvectors is ''graded''
has been observed in [1] and [2], however the results there were weaker than ours, and
these papers did not exploit this "graded" structure to any great extent. The basic
results on gradedness of eigenvectors are in Section 3.1 and the applications are in
Section 3.2.
Let Mm;n denote the space of m \Theta n real matrices , and let Mn j M n;n . For a symmetric
matrix H we let - 1 its eigenvalues, ordered
in decreasing order. For
its singular values. The only norm that we use is the spectral norm (or 2-norm)
and we denote it by k \Delta k, i.e., (X). When we say that a matrix has unit
columns we mean that its columns have unit Euclidean norm.
For a matrix or vector X, jXj denotes its entry-wise absolute value. For two
matrices or vectors X and Y of the same dimensions we use minfX; Y g to denote
their entry-wise minimum, and we use X - Y to mean that each entry of X is
smaller than the corresponding entry of Y . To differentiate between the component-wise
and positive semidefinite orderings we use A - B to mean that A and B are
A is positive semidefinite. We use E to denote a matrix of ones
and e to denote a column vector of ones-the dimension will be apparent from the
context.
In studying the perturbation theory of eigenvectors we use the two notions of the
relative gap between the eigenvalues that were introduced in [1], but we use different
notation. Given a positive vector - we define
and
relgap   (-;
One similarity between the two relative gaps is that it is sufficient to take the minimum
either case. However, it is easy to see that relgap   (-; i) is at
most 1, while relgap(-; i) can be arbitrarily large and that
then as we show at the end of the section
relgap   (-
Unfortunately the result for the perturbation to relgap is more complicated, and
this sometimes complicates analysis and results involving relgap. (See [2, proof of
Proposition 2.6] for such an instance.)
2 By this we mean that both kD
are not much larger than 1, where D
and D 1 are diagonal matrices such that the diagonal elements of D
1. We use quotes because this not the usual definition of gradedness, but, none-the-less it is related
to the gradedness of H and H 1 .
perturbation bounds for positive definite matrices 3
It is not clear which relative gap one should use, or whether one should use both,
or perhaps the relative gap used in [4]. In [2] it was suggested that relgap(-(H); i)
is the appropriate measure of the relative gap between - i (H) and the rest of the
eigenvalues of H, and that relgap(oe(G); i) is the appropriate measure of the relative
gap between oe i (G) and the rest of the singular values of G. The eigenvector results in
Theorems 3.5 and 2.9 and Corollary 2.10 and the singular vector results in in Theorem
2.8 suggest that this is not the case.
Luckily, one is most interested in the relative gap when it is small and in this
case it doesn't make much difference which definition one chooses. For example, if
then one can check that
One can also check that the left hand inequality is always valid by a simple application
of the arithmetic-geometric mean inequality.
Let us now prove (1.1). Define f on (0; 1) 2 by
Then
relgap   (-;
So in order to prove (1.1), it is sufficient to prove that for any - 1
which
we must have
Without loss of generality . The bound (1.3) implies that ~ - 1 - 2 . Since
~
Writing (1.6) as
~
~
one sees that f( ~ of as a function of ff 1 , and ff 2 , is minimized then
Substituting these values for ff 1 and ff 2 , substituting the
expressions (1.5) and (1.6) in (1.4) we see that it is sufficient to prove
4 roy mathias
or equivalently,
which is equivalent to
The left hand side of (1.9) is an increasing function of ffi and so in order to verify (1.9)
it is sufficient to verify it when ffi is as large as possible - that is when
Straight forward algebra shows that (1.9) holds with equality when one substitutes
this value of ffi . Thus we have verified (1.1). The bound (1.1) is a slight improvement
over [7, Proposition 3.3 equation (3.8)] in the case
2. A unified approach. In this section we give a unified approach to some of
the inequalities in [2] and [1]. This approach also allows one to bound the relative
perturbation in the eigenvalues of a positive definite matrix caused by a perturbation
in a particular entry.
The key idea in this section is to express the additive perturbation H + \DeltaH as
a multiplicative perturbation of H. Given a multiplicative perturbation of a matrix
it is quite natural that the perturbation of the eigenvalues and eigenvectors is also
multiplicative. It is then a small step from this multiplicative perturbation to the
component-wise perturbation bounds that we desire. There are two ways to write
\DeltaH as a multiplicative perturbation
and
possible choice of Y is H 1
.) If one wants to prove eigenvalue
inequalities it seems that both representations give the same bounds. If one uses the
representation (2.1) then Ostrowski's Theorem [6, Theorem 4.5.9] yields the relation
between the eigenvalues of H and H this is the route taken in [4]. We shall
use (2.2) and the monotonicity principle (Theorem 2.1) because the proofs are slightly
quicker. Demmel and Veseli'c [2] and Barlow and Demmel [1] used the Courant-Fisher
min-max representation of the eigenvalues of a Hermitian matrix to derive similar
results.
In Jacobi's method one encounters positive definite matrices
diagonal and A can be much better conditioned than
H. For this reason Demmel and Veseli'c assumed the matrices
D(\DeltaA)D with D diagonal to be the data in their work [2]. We consider a slightly
more general situation and just assume that H and H + \DeltaH are positive definite.
We consider this more general setting firstly to show that one can prove relative
perturbation bounds for positive definite matrices without assuming that the matrices
are graded and secondly because the results are slightly cleaner in the general case.
perturbation bounds for positive definite matrices 5
(For example, the statement of Theorem 2.9, which deals with the general case, is
cleaned than the statement of Corollary 2.10 which deals with the special case where
D is diagonal.) Lemma 2.2 allows us to derive their results as corollaries of ours.
Theorem 2.1. Monotonicity Principle [6, Corollary 4.3.3] Let A; B 2 Mn . If
The following lemma will be useful in applying our general results in special situations.
Lemma 2.2. Let H be positive definite and let \DeltaH be arbitrary. Let Y 2 Mn be
such that
Furthermore, if
Proof. Since Y Y
there must be an orthogonal matrix Q such that
Q. Thus
For the second part of the lemma take
2 and apply the first part. Then we
have
as required. 2
Note that if D is diagonal, as it will be in applications, then using
the notation of Lemma 2.2 we have
Our bounds are in terms of j while those of Demmel and Veseli'c in [2] are in terms
of the larger quantity kA They assumed that the diagonal elements of A
are all 1. This is not always necessary, though it is a good choice of A in that it
approximately minimizes kA We only assume that the diagonal elements
of A are 1 when it is necessary.
2.1. Eigenvalues and Singular Values. Our main eigenvalue perturbation
theorem is
Theorem 2.3. Let H; H +\DeltaH 2 Mn be positive definite and let
k.
Then
Proof. Write
2 . Since
6 roy mathias
we have
The monotonicity principle (Theorem 2.1) now gives the required bounds. 2
Using the second part of Lemma 2.2 we obtain a result that is essentially the
same as [2, Theorem 2.3]:
Theorem 2.4. Let
positive definite,
assume that D diagonal, and let
k. Then
As another corollary of the monotonicity principle we have a useful relation between
the diagonal elements of a positive definite matrix and its eigenvalues [2, Proposition
2.10]:
Corollary 2.5. Let Mn be a positive definite matrix and assume
that D is diagonal and that the main diagonal entries of A are all 1 while the main
diagonal entries of H are ordered in decreasing order. Then
Proof. Since -n (A)I - A - 1 (A)I it follows that -n (A)D 2 - DAD - 1 (A)D 2 .
The matrix D 2 is diagonal so its eigenvalues are its diagonal elements and these are
n. The result now follows from the monotonicity principle. 2
One would expect that the eigenvalues of H are more sensitive to perturbations in
some entries of H and less sensitive to perturbations in others. Stating the bound in
terms of
allows one to derive stronger bounds on the sensitivity
of the eigenvalues of H to a perturbation in any one of the entries (or two corresponding
off-diagonal entries) of H than if we had replaced j by
us assume the notation of the theorem.
is the unit n-vector with
ith component equal to 1. Suppose that that is a relative perturbation
of ffl in the jth main diagonal entry, then
and so
In fact, we can say more. and so, from the monotonicity
principle, we know than - i so the lower bound in (2.5) can
be taken as 1, and vice versa if ffl ! 0. If kA as is quite possible for
some values of j, then the bound (2.5) is much better than (2.3) with j replaced by
perturbation in entries ij and ji, then for any
perturbation bounds for positive definite matrices 7
Now taking
and so for
One may hope to prove a bound with j(A instead of of
2 . To
see that such a bound is not possible consider the case A = I. Then the off diagonal
elements of A \Gamma1 are 0, but clearly perturbing an off-diagonal element of A does change
the eigenvalues of DAD.
One can obtain similar bounds on the perturbation of the eigenvectors, singular
values and singular vectors caused by a perturbation in one of the elements of the
matrix. In the case of eigenvectors and singular vectors one can obtain norm-wise and
component-wise bounds. The bounds for singular values and singular vectors involve
a row of B is of full rank) rather than just one element
of the inverse (or pseudo-inverse).
2.2. Eigenvectors and singular vectors. Now let us see how this approach
gives norm-wise perturbation bounds for the eigenvectors of a graded positive definite
matrix in terms of the relative gap between the eigenvalues. Let H be positive definite.
Let U be an orthogonal matrix with jth column an eigenvector of H corresponding
to - j (H) and let   be a diagonal matrix with ii element - i (H). Then
H, the first part of Lemma
2.2 implies that
u be an eigenvector of   1
2 . Then ~ is an eigenvector of H+ \DeltaH .
The vector is an eigenvector of H and so the norm-wise difference between
u and ~
u is
So to show that ~
u can be chosen such that ku \Gamma ~ uk is small we must show that - u can
be chosen to be close to e j . We do this in Lemma 2.6, which follows easily from the
standard perturbation theory given in [5, pp. 345-6].
We have used the fact that U is orthogonal in (2.8), and hence has norm 1, to
obtain a norm-wise bound on u \Gamma ~
u. In Section 3.2 we use the component-wise bounds
on U to derive a component-wise bound on u \Gamma ~
u.
Lemma 2.6. Let  diagonal elements ordered in decreasing
order and assume that - j+1 be a symmetric matrix and let
8 roy mathias
fflX. Then for ffl sufficiently small - is distinct, and one
can choose -
u(ffl) to be an eigenvector of H(ffl) such that
and so
If we take
2 in Lemma 2.6 then one can see that the coefficient of ffl
on the right hand side of (2.11) is bounded by@ X
element of \Delta. Substituting j for k\Deltak from (2.7) we get
relgap(-;
?From (2.8) it follows that we have the same bound on ku \Gamma ~ uk.
We summarize the argument in the following theorem:
Theorem 2.7. Let H 2 Mn be positive definite and let
k. Let
Assume that - j (0) is a simple eigenvalue
of H. Let u be a corresponding unit eigenvector of H. Then, for sufficiently small ffl,
there is an eigenvector u(ffl) of H(ffl) corresponding to - j (ffl) such that
relgap(-;
As mentioned earlier, we may replace j by kA \Gamma1 kk\DeltaAk. The resulting bound
improves that in [2, Theorem 2.5] by a factor of
Eisenstat and Ipsen also give a bound on the perturbation of eigenvectors which
involves a relative gap [4, Theorem 2.2]. Their bound relates the eigenvectors of H
and those of KHK T , where K 2 Mn is non-singular. It is an absolute bound - not
a first order bound. To obtain a bound of the form (2.12) from [4, Theorem 2.2] one
must find a bound on k(H of the form
It is shown in [9] that if (2.13) is to hold for all n \Theta n H and \DeltaH with H positive
definite then the constant c must depend on n and must grow like log n. That is, a
direct application of [4, Theorem 2.2] to the present situation does not yield (2.12).
However one can derive (2.12) using the idea behind the proof of [4, Theorem 2.2]
and a more careful argument [3].
perturbation bounds for positive definite matrices 9
Veseli'c and the author have used ideas similar to those in this section to prove a
non-asymptotic relative perturbation bound on the eigenvectors of a positive definite
matrix [13].
One can apply Lemma 2.6 to GG T and G T G and thereby remove the factor
from the bound on the perturbation of the right and left singular vectors
given in [2, Theorem 2.16]. Note that one must apply Lemma 2.6 directly in order to
obtain the strongest result. If one applies Theorem 2.7 to G T G the resulting bound
contains an extra factor Notice that the bound on the right and left
singular vectors is not the same - the bound on the right singular vectors is potentially
much smaller since relgap can be much larger than relgap   .
Theorem 2.8. Let G; G+ \DeltaG 2 M m;n and let G y be the pseudo-inverse of G.
Assume that G is of rank ng and and that \DeltaG = \DeltaGG y G.
and assume that oe j (G) is simple.
Let u and v be left and right singular vectors of G corresponding to oe j (G). Then for
sufficiently small ffl, there are left and right singular vectors of G(ffl), u(ffl) and v(ffl)
corresponding to oe j (G(ffl)) such that
relgap   (oe 2 (G);
Proof. Let U \SigmaV T be a singular value decomposition of G - here u and V are
square and \Sigma is rectangular. First let us consider the right singular vectors, which
are the eigenvectors of G T G.
and hence has norm at most 2k\DeltaGG y
Now from (2.11) one can choose ~ u a jth eigenvector of \Sigma T that differs in
norm from e j by at most
to first order in ffl. Hence, we have the same bound on ku \Gamma V ~
uk to first order in ffl.
The vector V ~
u is an eigenvector (corresponding to jth eigenvalue) of
which is equal to G T (ffl)G(ffl) up to O(ffl 2 ) terms. Since the jth singular value of G(ffl)
is simple, it follows that V ~ u is a right singular vector of of G(ffl) up to O(ffl 2 ).
Now let us consider the left singular vectors. As above we can show that
roy mathias
U and has norm at most j. So by (2.11) there is an eigenvector
of that differs from e j in norm by at most
to first order in ffl. In the same way as before we can now deduce that there is a vector
v(ffl) with this distance of v. 2
2.3. Distance to nearest ill-posed problem. It was shown in [1, Proposition
9] that relgap(-(H); i) is approximately the distance from H to the nearest matrix
with a multiple ith eigenvalue in the case that H is a scaled diagonally dominant
symmetric matrix and distances are measured with respect to the grading of H. We
show that there is a similar result for positive definite matrices. In Theorem 2.9 we
show that relgap(-(H); i) is exactly the distance to the nearest matrix with a repeated
ith eigenvalue when we use the norm
k. We strengthen [1,
Propostion 9] in Corollary 2.10 - our upper and lower bounds on the distance differ
by a factor of -(A) while those in [1, Proposition 9] differ by a factor of about - 4 (A),
a potentially large difference. Our bound is considerably simpler than that in [1], it
doesn't involve factors of n (although one could replace by n) and it's validity
doesn't depend on the value of the relative gap (the bound in [1] has the requirement
diagonal examples show that not every eigenvalue of H will have
the maximum sensitivity - \Gamma1
and so this difference in the upper and lower bounds
is to be expected. That is to say that one cannot hope to improve the bound (2.17)
by more than a factor of n. Our bound involves relgap   while the bound in
[1] involves relgap. All these reasons suggest that relgap  \Gamma1 , and not relgap \Gamma1 , is the
right measure of the distance to the nearest problem with a repeated ith eigenvalue.
Theorem 2.9. Let H be positive definite. Let - i (H) be a simple eigenvalue of
H, so that relgap   (-
\DeltaH ) is a multiple eigenvalue of H
Then
Proof. First we show that ffi - relgap   (-(H); i). Let \DeltaH be a perturbation
that attains the minimum in the definition of ffi . Then
k. Let
n. By Theorem 2.3 we know that
Since \DeltaH has a multiple ith eigenvalue there is an index j 6= i for which - 0
. By
(2.16) we must have
perturbation bounds for positive definite matrices 11
which implies
relgap   (-(H); i) -
Now we show that Choose a value j such that
(One can easily show that this is possible.) Set
where x i and x j are unit eigenvectors of H corresponding to - i and - j . One can check
that \DeltaH). Because x i and x j are eigenvectors of H
Because x i and x j are orthogonal it follows that
as required. 2
Corollary 2.10. Let positive definite and assume that
D is diagonal and that the main diagonal entries of A are 1. Let - i (H) be a simple
eigenvalue of H, so that relgap   (-
\DeltaH) is a multiple eigenvalue of H+ \DeltaHg:
Then
Proof. Because
and because, by Lemma 2.2, we have
it follows that
The result now follows from Theorem 2.9. 2
3. Eigenvector Components. It was shown in [1] that the eigenvectors of a
scaled diagonally dominant matrix are scaled in the same way as the matrix. Essentially
the same proof yields [2, Proposition 2.8]. We strengthen these by a factor -(A)
in Corollaries 3.2 and 3.3. In Section 3.2 we strengthen many of the results in [2]
by using the stronger results in Section 3.1, and show that the growth factor in the
error bound on the eigenvectors computed by Jacobi's method is linear rather than
exponential (Theorem 3.8). We also give improved component-wise bounds for the
perturbation of singular vectors (Theorems 3.6 and 3.7). It is essential that the D i
be diagonal in this section as we are considering the components of the eigenvectors.
roy mathias
3.1. Gradedness of eigenvectors. Here we give some simple results on the
"graded" structure of an orthogonal matrix that transforms one graded positive definite
matrix into another, and use this to derive results on the eigenvectors of a graded
positive definite matrix.
Lemma 3.1. Let H where the main diagonal
entries of the A i are 1 and the D i are diagonal. Assume that H 0 2 Mn and H 1 2 Mm
are positive definite. Then
Proof. It is easy to check that
Now, using the fact that the main diagonal entries of A 1 2 Mm are all 1 for the first
inequality, and the monotonicity principle (Theorem 2.1) applied to -n
1 for the second, we have
Taking square roots and dividing by - 1n the asserted bound. 2
If the matrix C is orthogonal then H
so we have a companion bound stated in the next result.
Corollary 3.2. Let H where the main
diagonal entries of the A i are 1 and the D i are diagonal. Assume that U is orthogonal.
Then
This says that if an orthogonal matrix U transforms H 0 into H 1 and -n (D \Gamma1
are not too small then U has a "graded" structure.
In the special case that U is the matrix of eigenvectors of
and we obtain
n:
It is useful to have bounds on the individual entries of U and we state a variety of
such bounds in (3.5-3.7), but note that they are actually weaker than the norm-wise
bounds in (3.4). The bounds (3.5-3.7) are stronger than those in [2, Proposition
2.8] and [1, Proposition 6] which have a factor - 3=2 (A) rather than - 1
2 (A) on the
right hand side. The result in [1] is however applicable to scaled diagonally dominant
symmetric matrices while our result is only for positive definite matrices.
Corollary 3.3. Let positive definite and assume that D
is diagonal and that the main diagonal entries of A are 1. Let U be an orthogonal
matrix such that  diagonal with diagonal entries - i . Then
r
s
perturbation bounds for positive definite matrices 13
s
r
s
r
and the first inequality is stronger than the second and third.
Proof. The fact that ju ij j is no larger than the first (second) quantity on the right
hand side of (3.5) follows from the first (second) inequality in (3.4). The remaining
inequalities can be derived from (3.5) using the relations between the eigenvalues of H
and its main diagonal entries in Corollary 2.5. This also shows that they are weaker
than (3.5). 2
Another way to state the bound in (3.5) is
where the minimum is taken component-wise. Recall that E is the matrix of ones.
3.2. Applications of "graded" eigenvectors. Now we use the results in Section
3.1 to give another proof of the fact that components of the eigenvectors of a
graded positive definite matrix are determined to a high relative accuracy, then show
that relgap   (-(H); i) is a good measure of the distance of a graded matrix from the
nearest matrix with a multiple ith eigenvalue, where the distance is measured in a
norm that respects that grading, and finally that Jacobi's method does indeed compute
the eigenvectors to this accuracy (improving on [2, Theorem 3.4]).
We now combine lemma 2.6 with the general technique used in Section 2 to obtain
a lemma that will be useful in proving component-wise bounds for eigenvectors and
singular vectors.
Lemma 3.4. Let  diagonal elements ordered in decreasing
order and assume that - j+1 be a symmetric matrix and let U be
an orthogonal matrix.
be an eigenvector
of H j H(0) associated with - j . Let -
u be the upper bound on the jth eigenvector,
that is,
r
s
g:
Then, for ffl sufficiently small, - is simple, and one can choose u(ffl) to
be a unit eigenvector of H(ffl) corresponding to - j (ffl) such that
relgap   (-;
Proof. Since U is the matrix of eigenvectors of H, the bound (3.5) gives
r
r
g:
Note that the vector -
u defined in the statement of the theorem is just the jth column
of the matrix -
U just defined in (3.10). ?From Lemma 2.6 it follows that there is an
eigenvector -
u(ffl) such that
14 roy mathias
where r is the vector given by
is the element of X. Let
u(ffl). So
and we must now bound -
Ur. The ith element of -
Ur is
min
r
r
min
r
s
r
s
min
r
s
For the final equality note that the quantity
min
r
s
is now independent of k and is -
defined in the statement of this lemma. 2
This result gives component-wise perturbation bounds for eigenvectors and singular
vectors as simple corollaries.
Theorem 3.5. Let positive definite and let
and assume that
it is a simple eigenvalue of H. Let u be a corresponding unit eigenvector of H. Let - u
be the upper bound on the jth unit eigenvector, that is ,
r
s
g:
Then, for sufficiently small ffl, - j (ffl) is simple and there is a unit eigenvector u(ffl) of
H(ffl) corresponding to - j (ffl) such that
relgap   (-;
perturbation bounds for positive definite matrices 15
Proof. Write
where U is the matrix of eigenvectors of H and
implies that j. The asserted bound now follows from Lemma 3.4. 2
Lemma 3.4 also yields a component-wise bound on singular vectors.
Theorem 3.6. Let m;n be of rank n and let
Assume that oe j is simple
and that v is a corresponding unit right singular vector. Let - v be the upper bound on
the jth right unit singular vector, that is
g:
Then, for sufficiently small ffl, oe j (ffl) is simple and there is a unit right singular vector
v(ffl) of G(ffl) corresponding to oe j (ffl) such that
relgap   (oe
Proof. Let has orthonormal columns, \Sigma 2 Mn is
positive diagonal and V 2 Mn is orthogonal. We may write
is the pseudo-inverse of B. Note
that kFk - 2j. Since the jth singular value of G is simple the corresponding singular
vector is differentiable and so in particular, v(ffl), the jth singular vector of G(ffl) (and
eigenvector of G(ffl) T G(ffl)) and -
v, the jth eigenvector of V \Sigma T differ by
at most O(ffl 2 ). According to Lemma 3.4, we know that
relgap   (oe
and hence the bound on v(ffl). 2
This improves [2, Proposition 2.20] in two ways. Firstly, our upper bound - v j is
smaller than that in [2] by a factor of about oe \Gamma1
n (B), and secondly, we have a factor
in the denominator while in [2] there is a factor oe 2
our bound
is smaller by a factor of about oe \Gamma2
(B). The latter difference arises because in [2] the
authors used the equivalent of Theorem 3.5 applied to G T G, whereas we use Lemma
3.4.
The quantity relgap   (oe can be hard to deal with when one perturbs G, and
hence also its singular values. It would be more convenient to have relgap   (oe;
the bound. It is easy to check that relgap   (oe;
It is worth stating the stronger form of the inequality (3.11) as this is more natural
when G is the Cholesky factor of a positive definite H (as is the case in [12]) . In this
case oe 2
roy mathias
Because we have no component-wise bound on the left singular vectors of
we cannot get a component-wise bound on the difference between the left singular
vectors of BD and (B \DeltaB)D.
We now give a result on component-wise perturbations of singular vectors. Our
bound is stronger than [2, Propositions 2.19 and 2.20] by a factor of about oe \Gamma3
upper bound - v is smaller than than in [2] by a factor of oe \Gamma2
n (B), and the denominator
here contains a factor oe n (B) while that in [2] contained oe 2
(B)). We could give an
improved bound for eigenvectors also, but we restrict ourselves to the case of singular
vectors because that is what is important when one uses one sided Jacobi to compute
eigenvectors of a positive definite matrix to high component-wise relative accuracy.
Theorem 3.7. Let have rank n and assume that
are positive and that B has unit columns. Choose
ng and let v be a unit right singular vector corresponding to oe i (G). Let
\DeltaBD and set
Then
and there is a vector -
v that is a right singular vector of G+ \DeltaG such that
Proof. The statement that - v is an upper bound on v follows from (3.5). Let
t\DeltaG. The condition ensures that oe i (G(t)) is simple
so there is a differentiable v(t) that is a right singular vector of G(t) such
that and, from (3.12) we have the component-wise bound
dt v(t)
and B(t) has unit columns and D(t) is positive diagonal. So
for a bound on jv \Gamma - need only bound each of the quantities that
depend on t and then integrate the bound. Using the fact
one can can show that for t 2 [0; 1]
relgap   (oe(G(t));
One can check that
The condition
necessarily less than 1. We use this in the final inequality in the display below.
perturbation bounds for positive definite matrices 17
Using (3.5) for the first inequality and bounds on oe j (G(t)); oe n (B(t)) and d i (t) for the
subsequent inequalities we have
Substituting these bounds into (3.14) gives
dt
which when integrated yields the asserted inequality. 2
In right handed Jacobi one computes the singular values of G 0 2 Mn by generating
a sequence G is an orthogonal matrix chosen to orthogonalize two
columns of G i . One stops when
One can obtain the right singular vectors of G by accumulating the J i . Demmel and
Veseli'c show in [2, Theorem 3.4] that when implemented in finite precision arithmetic
this algorithm gives the individual components of the eigenvectors to a high accuracy
relative to their upper bounds (actually this is for two sided Jacobi, but the proof is
essentially the same for 1 sided Jacobi). However, their bound contains a factor for
which they say "linear growth is far more likely than exponential growth". In the
next result we show that the growth is indeed linear. One can prove an analogous
result for two sided Jacobi applied to a positive definite matrix.
Let us denote the product J i J by J i:k . The key idea that allows us
to derive a growth factor that is linear in M rather than exponential in M is that
we bound J i:k directly, rather than bound it by jJ i:k j - jJ i jjJ
bounding each of the terms on the right hand side. This idea has been used profitably
in [11] also.
Theorem 3.8. Let G has unit columns
and D i is diagonal. Assume that
where J i is orthogonal and
Assume further that the columns of GM are almost orthogonal in the sense that GM
satisfies (3.15) with tolerance tol. Let
and assume that
be the computed column
of J 0:M \Gamma1 corresponding to oe j (G). Then there is a unit right singular vector u T of G
roy mathias
corresponding to oe j (G) such that, to first order in j; ffl; and tol,
oe \Gamma2
min
relgap   (oe(G);
where
is the upper bound on u from (3.5).
The bound (3.16) is a first order bound. The proof below would also yield a
bound that takes into account all the higher order terms, but the resulting inequality
would be much more complicated and probably not any more useful.
If the G i and J i arise from right handed Jacobi applied to G in finite precision
arithmetic with precision ffl then one can take Theorem 4.2 and the
ensuing discussion].
Let us compare our bound with
relgap   (oe(G);
min
which is essentially the bound on the computed right singular values from [2, Theorem
4.4] stated in our notation. Our bound is stronger in several respects. The term
q(M; n) is a growth factor that is exponential in M , while our bound is linear in M .
As we have mentioned earlier, the upper bound vector - u in (3.17) is larger than -
u by
a factor of about oe \Gamma2
n (B), which could be quite significant. Also, we have two terms,
one in oe \Gamma2
min and the other in (oe min \Delta relgap   (oe(G); these quantities are less
than (oe 2
min relgap   (oe(G); which occurs in (3.17).
A weakness of both bounds is that they contain the factor oe \Gamma1
min (defined in the
statement of the theorem) rather than oe
n (B). It has been observed experimentally
[2, Section 7.4] that oe min =oe n (B) is generally 1 or close to 1, but no rigorous proof of
this fact is known. Mascarenhas has shown that the ratio can be as large as n=4 [8].
One can also see that for a given ffl we can take tol, the stopping tolerance, as large
as ffloe \Gamma1
significantly increasing the right hand side of (3.16). Typically, it
is suggested that one take tol to be a modest multiple of ffl when one wants to compute
the eigenvectors or eigenvalues to high relative accuracy [2]. Thus this larger value of
tol may be useful in practice to save little computation through earlier termination.
The rest of the paper is devoted to the rather lengthy proof of this theorem.
Proof. The outline of the proof is as follows. First we will bound ju \Gamma -
uj where u
is the value of the jth column of J 0:M \Gamma1 computed in exact arithmetic. Next we will
is for true) is an exact singular vector of G associated
with oe j (G). The inequality (3.16) follows by combining these two bounds. Through
out we will use the facts that oe j (GM
min and
Now consider
uj. This bound depends only on the scaling of the J i:k and
is independent of relgap   (oe(G); j). If X;Y 2 Mn are multiplied in floating point
arithmetic with precision ffl the result is XY
Using this fact one can show by induction that
(3.
perturbation bounds for positive definite matrices 19
is the error in multiplying J 0:i\Gamma1 and J i and
is the first order effect of this error in the computed value of J 0:M . Taking
absolute values in (3.18) gives the component-wise error bound
Now
(D 0 jJ
noe
noe
noe
noe
min E:
Recall that E denotes the matrix of ones. We have used the first term in (3.8) and the
fact that, up to first order, J i+1:M \Gamma1 diagonalizes G T
for the first inequality,
(3.2) twice for the third. Since GM has orthogonal columns, up to O(tol), and the
singular values of GM are the same as those of G to O(j) it follows that DM = \Sigma, at
least to first order. So, multiplying by D 0 and \Sigma \Gamma1 , we have, to first order
min fflE:
In the same way, we obtain the first order bound
min fflE:
These two bounds can be combined to give
min
where the minimum is taken component-wise. (Note that D D.) The jth column
of this is the inequality we desire:
u:
This completes the first step.
Now let us bound the error between u and a singular vector of G. If the columns of
GM were orthogonal then in particular e j would be a right singular vector associated
with oe j (GM ). If in addition all the \DeltaG i were 0 then
would be a right singular vector associated with oe j (G). Neither of these
hypotheses is true, though in each case they are 'almost true' and so u is close to
being a singular vector of G 0 . We now bound he difference.
First we will consider the fact that the columns of GM are not exactly orthogonal.
Write
Then each entry of A is at most tol in absolute value and so tol. The equation
(3.20) implies that there is an orthogonal matrix Q such that
One can check that
roy mathias
we will use this bound later.
Now consider the effect of the \DeltaG i . It is easy to check, by induction for example,
that
where
Now, using the assumption k\DeltaG
for the first inequality and (3.2) for the
second we have
Together with (3.21) this yields
Now we will combine these two results to show that GM + \DeltaG has a right singular
vector close to e j and hence that G
0:M \Gamma1 has a right singular vector
close to . The right singular vectors of GM + \DeltaG are the same as those
of Q(GM is the orthogonal matrix introduced after equation (3.20).
Also,
The jth right singular vector of DM is e j and
So by Theorem 3.7 there is a right singular vector v of G+ \DeltaG corresponding to its
jth singular value such that
where
Now let us drop the second order terms in (3.22) and - v. The term - is
O(tol)oe 1 (BM ) so we may drop all first order terms in - v and in the ratio in (3.22).
In particular we may replace oe n (BM
all by 1. We do not
perturbation bounds for positive definite matrices 21
assume that relgap   (oe(G M ); j) is large with respect to j and - so we cannot replace
relgap   (oe(G M ); However, as was shown at the end of
the introduction, we have
relgap   (oe(G M );
min
and hence
relgap   (oe(G M );
these substitutions we obtain the bound that is
equivalent to (3.22) up to first order
relgap   (oe(G M );
where
For convenience, let the coefficient of - v in (3.23) be denoted by c.
construction it is a right singular vector of G 0 corresponding
to oe j (G 0 ). Now we can complete the proof by bounding
We have used a slight generalization of (3.5) for the penultimate inequality and have
dropped second order terms in the last inequality. Similarly,
and so
Now combine the bound on ju \Gamma u

Acknowledgment

I thank the referee whose detailed comments, including
the observation that grading is not necessary for relative perturbation bounds, have
greatly improved the presentation of the results in this paper.



--R

Computing accurate eigensystems of scaled diagonally dominant

Jacobi's method is more accurate than QR.
personal communication.
Relative perturbation techniques for singular value problems.

Matrix Computations.

Matrix Analysis.
Relative perturbation theory: (I) eigenvalue and singular value variations.

A note on Jacobi being more accurate then QR.
A bound for the matrix square root with application to eigenvector perturbation.
Matrix Anal.
Accurate eigensystem computations by Jacobi methods.
Instability of parallel prefix matrix multiplication.
Fast accurate eigenvalue computations for graded positive definite matrices.
A relative perturbation bound for positive definite matrices.
--TR
jacobi's method;symmetric eigenvalue problem;error analysis;perturbation theory;positive definite matrix;graded matrix