Relative perturbation of invariant subspaces^{∗}

Ninoslav Truhar^{†}and Ivan Slapničar^{‡}

Abstract. In this paper we consider the upper bound for the sine of the greatest canonical angle between the original invariant subspace and its perturbation. We present our recent results which generalize some of the results from the relative perturbation theory of indefinite Hermitian matrices.

Key words: perturbation bound, invariant subspace, relative perturbations, indefinite Hermitian matrix

Sažetak. Relativna perturbacija invarijantnih potprostora. U ovom radu analiziramo gornje ograde za sinus najvećeg kanonskog kuta izmed̄u originalnog invarijantnog potprostora i njegove perturbacije. Prikazat ćemo naše posljednje rezultate koji generaliziraju neke rezultate iz relativene perturbacijske teorije indefinitnih hermitskih matrica.

Ključne riječi: perturbacijska ograda, invarijantni potprostor, relativne perturbacije, indefinitna hermitska matrica

This paper contains the lecture which is a natural continuation of the last lecture presented at the Mathematical Colloquium in Osijek in the winter semester 1995/1996. (see [12]). Here we will present our most recent results from relative perturbation of an invariant subspace (see [13, 11]).

In this paper we consider properties of the perturbation bounds for the spectral projection of a Hermitian matrix H of order n. Our perturbation results generalized some of the results of Veselić and Slapničar [14, 8, 7], and Ren-Cang Li [5].

Veslić and Slapničar consider norm-estimates of the eigenprojections corresponding to one eigenvalue λ (possibly multiple). We generalize these results on the spectral projections corresponding to the set of the neighboring eigenvalues.

We will derive a bound for

dist(X , X̃) = ∥P_{X} − PX̃∥ = sinθ_{1},  (1)

where P_{X} is an orthogonal projection on the subspace X , θ_{1} is the greatest canonical angle between subspaces X and X̃ (see [4] or [10]) and ∥ · ∥ is a standard 2-norm.

∗The lecture presented at the Mathematical Colloquium in Osijek organized by Croatian Mathematical Society - Division Osijek, May 31, 1996.

†Faculty of Civil Engineering, University of Osijek, Drinska 16 a, HR-31000 Osijek, Croatia, e-mail: truhar@most.gfos.hr

‡Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture, University of Split, R. Boškovića b.b., HR-21000 Split, Croatia, e-mail: ivan.slapnicar@fesb.hr

We consider behavior of the invariant subspace X spanned by eigenvectors corresponding to eigenvalues λ_{i}, ..., λ_{i+k} under perturbation of the matrix H.

The perturbation matrix δH satisfies

|x^{∗}δH x| ≤ η x^{∗} H x,  η < 1.  (2)

Here all eigenvalues of the matrix H and H̃ = H + δH are given in the same increasing order, λ_{1} ≤ λ_{2} ≤ ... ≤ λ_{n}, and λ̃_{1} ≤ λ̃_{2} ≤ ... ≤ λ̃_{n}.

Veselić and Slapničar [14] proved the following result for perturbation of eigenvalues: if

H = D A D, H = D Â D, H = \sqrt{H^{2}},

where D is any scaling matrix, i.e. a positive definite diagonal matrix. The scaling D is typically, but not necessarily of the standard form D = (diag( H ))^{1/2}. Then (2) implies

1 − η ≤ \frac{λ̃_{j}}{λ_{j}} ≤ 1 + η, za  1 ≤ j ≤ n,  (3)

where λ_{j} and λ̃_{j} are j − th eigenvalues of H and H̃ = H + δH, respectively. They showed that for perturbations such as

|δH_{ij}| ≤ ε|H_{ij}|,  (4)

the inequality (3) holds with

η = ε∥ |A| ∥ ∥Â^{−1}∥ < 1.  (5)

The perturbations (4) are called floating-point perturbations.

Let T be the set of the k + 1 neighbouring eigenvalues (some of them can be mutually equal) T = {λ_{i}, λ_{i+1}, ..., λ_{i+k}}.

Our perturbation bound for (1) is given by

\begin{aligned}sin θ_{1} = ∥ δP ∥ & ≤ & \frac{1}{2} (\frac{λ_{i+k}}{λ_{i}} ( \frac{1}{rg(T )} + 1 ) + 1 − \frac{1}{rg(T )}) \\ & & · \frac{η}{rg(T )} \frac{1}{1 − \frac{η}{rg(T )}} , \end{aligned}  (6)

where η < rg(T ), provided that the right-hand side in (6) is positive.

The relative gap in (6) is defined by

rg(T ) = min \{\frac{λ_{i} − λ_{L}}{λ_{i} + \sqrt{λ_{i}|λ_{L}|}}, \frac{λ_{R} − λ_{i+k}}{λ_{R} + λ_{i+k}} , 1\} .  (7)

Further, for a special kind of indefinite Hermitian matrices we can get a much more accurate bound for norm-estimate of the spectral projection than in a general case. This class includes positive definite Hermitian matrices as a special case.

Let X be the invariant subspace of the indefinite Hermitian matrix H corresponding to the first k + 1 positive eigenvalues 0 < λ_{i} ≤ ... ≤ λ_{i+k}. Let X̃ be its perturbation. The perturbation bound for the sine of the greatest canonical angle between X and X̃ is in this case given by

sin θ_{1} =∥δP ∥ ≤\begin{cases}\frac{3}{2} \frac{\sqrt{λ_{i+k}}}{\sqrt{λ_{R}} − \sqrt{λ_{i+k}}} · \frac{η}{1 − 2 · η} , & for 2\sqrt{λ_{i+k}} ≤ \sqrt{λ_{R}} ≤ \frac{1}{2}\sqrt{|λ_{L}|}, \\ & or 2\sqrt{λ_{i+k}} ≤ \sqrt{λ_{R}} and \\ & λ_{L} doesn′t exist, \\ 3\frac{\sqrt{λ_{i+k}}}{\sqrt{|λ_{L}|} − 2\sqrt{λ_{i+k}}} · \frac{η}{1 − 2 · η} , & for 2\sqrt{λ_{i+k}} ≤ \frac{1}{2}\sqrt{|λ_{L}|} \\ & and λ_{R} doesn′t exist, \end{cases}

provided that the right-hand side is positive. Here the relative gap rg(T ) is defined by

rg(T ) = \frac{\sqrt{λ_{R}} − \sqrt{λ_{i+k}}}{\sqrt{λ_{R}}} ,

where λ_{R} = λ_{i+k+1} (i.e. right neighbor of λ_{i+k}).

For the positive definite Hermitian matrix H our approach gives a perturbation bound with the same accuracy like Ren-Cang Li’s [5], or for simple eigenvalues like Demmel and Veselić’s [3].

Also, we will show a perturbation bound for spectral projections of the factorized Hermitian matrix

H = G J G^{∗},

where G is an n×r matrix of the full column rank, and J is a non-singular Hermitian matrix, under the perturbation of the factor G. Our result is a natural extension of those from Slapničar and Veselić [14] on spectral projections corresponding to eigenvalues from the set T = {λ_{i}, λ_{i+1}, ..., λ_{i+k}}. Like in [14], the perturbed matrix H̃ is defined by

H̃ ≡ G̃J(G̃)^{∗} = (G + δG) J (G + δG)^{∗},  (8)

where

∥δGx∥ ≤ η∥Gx∥,  (9)

for all x and η < 1. The most common J is of the form

J = [ \begin{matrix}I_{m} & 0 \\ 0 & −I_{r−m} \end{matrix} ] ,

in which case m, r − m, and n − r is the number of the positive, negative and zero eigenvalues of H, respectively.

As we can see in [8], the perturbation of the type (9) occurs, for example, whenever G is given with a floating-point error in the sense

|δG_{ij}| ≤ ε |G_{ij}| for all i, j.

Then (9) holds with

η = \frac{\sqrt{n} ε}{σ_{min}(B)} < 1,  (10)

where G = B D and D is a non-singular diagonal scaling. As it is shown in [14], (8) and (9) imply

(1 − η)^{2} ≤ \frac{λ̃_{k}}{λ_{k}} ≤ (1 + η)^{2},  (11)

where λ_{k} and λ̃_{k} are equally ordered eigenvalues of H and H̃, respectively.

Let X be an invariant subspace of H spanned by eigenvectors corresponding to eigenvalues from the set T .

Our perturbation bound for the sine of the greatest canonical angle between the invariant subspace X and its perturbation X̃ is given by

\begin{aligned}sin θ_{1} = ∥ δP ∥ & ≤ & \frac{1}{2} ( \frac{λ_{i+k}}{λ_{i}} \frac{1}{rg_{G}(T )} + \frac{2 rg_{G}(T ) − 1}{rg_{G}(T )} ) \\ & & · η̃( 1 + \frac{1}{rg_{G}(T )} ) · \frac{1}{1 − \frac{η̃}{rg_{G}(T )}} , \end{aligned}  (12)

where η̃ = η(2 + η), provided that the right-hand side in (12) is positive, i.e. η̃ < rg_{G}(T ). The relative gap rg_{G}(T ) is defined by

rg_{G}(T ) = min \{\frac{λ_{i} − λ_{L}}{λ_{i} + |λ_{L}|}, \frac{λ_{R} − λ_{i+k}}{3 λ_{R} − λ_{i+k}} , \frac{1}{3}\} ,

where λ_{L} and λ_{R} denote the left and the right neighbor of λ_{i} and λ_{R}, in the spectrum σ(H) of H, respectively (i.e. λ_{L} = λ_{i−1}, λ_{R} = λ_{i+k+1}, for i > 1, i + k < n − 1). If λ_{L} (λ_{R}) does not exist, then there does not exist a corresponding member in definition of the relative gap rg_{G}(T ).

Further, one can use results from the above theory to derive the perturbation bound for a singular subspace of the matrix G. We will consider the perturbation of the Hermitian matrix H = G G^{∗}, where G is an n × r matrix with the full column rank. Let

H̃ = (G + δG) (G + δG)^{∗},

be a perturbed matrix, where

∥δG x∥ ≤ η ∥G x∥.

Our perturbation bound for the left singular subspace spanned by singular vectors corresponding to the first k − 1 singular values has a form

sin θ_{1} = ∥ δP ∥ ≤ \frac{λ_{k}}{λ_{k} − λ_{L}} ( 1 + \frac{1}{rg_{G}(T )} ) · \frac{η̃}{1 − \frac{η̃}{rg_{G}(T )}} ,

where η̃ = η · (2 + η), provided that the right-hand side is positive. The relative gap is here defined by

rg_{G}(T ) = \frac{λ_{k} − λ_{L}}{λ_{k} + λ_{L}} ,

where λ_{L} is the left neighbor of λ_{k} in the spectrum σ(H) of H (i.e. λ_{L} = λ_{k−1}).

Using the perturbation bound for a positive definite matrix and the fact that eigenvectors of the matrix K = G^{∗}G are left singular vectors of the matrix G, we will prove the perturbation bound for perturbation of a right singular subspace corresponding to the last k + 1 singular values.

Finally, we will show an indefinite version of the additive perturbation Theorem 4.6 of Ren-Cang Li [5]. In [5] Ren-Cang Li gives several generalizations of perturbation results from the standard perturbation theory of Devis and Kahan [2] and the relative perturbation theory of Barlow and Demmel [1] and Demmel and Veselić [3]. However, we obtain a perturbation bound for an invariant subspace corresponding to the first k eigenvalues of an indefinite Hermitian matrix. Our bound is similar to the bound of Ren-Cang Li [5], but we have a new gap.

Let H = D^{∗}AD and H̃ = D^{∗} (A+δA) D be two n×n Hermitian matrices, where D is non-singular. Here we assume that A is non-singular and ∥A^{−1}∥ ∥δA∥ ≤ 1 and that there exist α and δ > 0 such that

max_{1≤i≤k} λ_{i} ≤ α and min_{k+1≤j≤n} λ̃_{j} ≥ α + δ.

Then for any unitary invariant norm ∥ · ∥ and ∥ · ∥_{F} Frobenius norm

∥ sin Θ∥_{F} ≤ \frac{∥A^{−1}∥ ∥δA∥_{F}}{\sqrt{1 − ∥A^{−1}∥ ∥δA∥}} · \frac{∥V_{1}∥ ∥Ṽ_{2}^{∗}∥}{NewGap},

where Θ is a matrix of canonical angles between the invariant subspace X spanned by eigenvectors corresponding to the first k eigenvalues λ_{1}, ..., λ_{k} and its perturbation X̃ (see [10]) and

NewGap = min_{i,j} \frac{|λ̃_{j} − λ_{i}|}{\sqrt{|λ̃_{j}| · |λ_{i}|}}.  (13)

Matrices V_{1} and Ṽ_{2} are obtain by hyperbolic singular value decomposition and we will not explain here their structure (see [6], [13]). It is worth mentioning that ∥V_{1}∥ ∥Ṽ_{2}∥ is in practice very small. There is also theoretical uper bound for this factor [9] but this bound is of the lesser importance for our application since the actual values of ∥V_{1}∥ ∥Ṽ_{2}∥ are in practice in many cases much lower than predicted by this bound.

Using same approach one can easily prove a similar result for an indefinite Hermitian matrix H given in factorised form H = G J G^{∗}, perturbed by factor G, i.e. H̃ = G̃ J G̃^{∗}, where G = G + δG. Here we assume that G is a non-singular matrix and J is a diagonal matrix with ±1 on its diagonal.

Let X be a subspace spanned by eigenvectors corresponding to the first k eigenvalues of the matrix H. Let X̃ be perturbation of X . Let α and δ > 0 be such that

max_{1≤i≤k} λ_{i} ≤ α and min_{k+1≤j≤n} λ̃_{j} ≥ α + δ,

and let ∥G^{−1}∥ · ∥δG∥ < 1. Our perturbation bound for the sine of the greatest canonical angle θ_{1} is given by:

sin θ_{1} ≤ \frac{2 ∥G^{−1}∥ ∥δG∥ + ∥G^{−1}∥^{2} ∥δG∥^{2}}{1 − ∥G^{−1}∥ ∥δG∥} · \frac{1}{NewGap},

where NewGap is defined by (13).

References

[1] J. Barlow, J. Demmel, Computing Accurate Eigensystems of Scaled Diagonally Dominant Matrices, SIAM J. Num. Anal. 27(1990), 762–791.

[2] C. Davis, W. M. Kahan, The Rotation of Eigenvectors by a Perturbation. III, SIAM J. Num. Anal. 7(1970), 1–46.

[3] J. Demmel, K. Veselić, Jacobi’s Method is More Accurate than QR, SIAM J. Matrix Anal. Appl. 13(1992), 1204–1244.

[4] G. H. Golub, C. F. Van Loan, Matrix Computation, Johns Hopkins, Baltimore, 1989.

[5] Ren-Cang Li, Relative Perturbation Theory: (ii) eigenspace variations, Technical report, Department of Mathematics, University of California at Berkeley, 1994.

[6] R. Onn, A. O. Steinhardt and A. Bojanczyk, Hyperbolic singular value decompositions and applications, IEEE Trans. on Acoustics, Speech, and Signal Processing, (1991), 1575–1588.

[7] I. Slapničar, Accurate Symmetric Eigenreduction by Jacobi Method, Ph. D. thesis, Fernuniversität, Hagen, 1992.

[8] I. Slapničar, K. Veselić, Perturbations of the Eigenprojections of a Factorised Hermitian Matrix, Linear Algebra Appl. 218(1995), 273–280.

[9] I. Slapničar and K.Veselić, Bound for the condition of hyperbolic and symplectic eigenvector matrices, preprint, University of Split and Fenruniversität Hagen, (in preparation), 1996.

[10] G. W. Stewart, Ji-Guang Sun, Matrix Perturbation Theory, Academic Press, 1990.

[11] N. Truhar, Perturbacije invarijantnih potprostora, M. S. thesis, University of Zagreb, Zagreb, 1995.

[12] N. Truhar, Perturbacije invarijantnih potprostora, Mathematical Communications 1(1996) 51–60.

[13] N. Truhar, I. Slapničar, Relative Perturbation of Invariant Subspaces, Technical report, University of Osijek and University of Split, 1995, in preparation.

[14] K. Veselić, I. Slapničar, Floating - point Perturbation of Hermitian Matrices, Linear Algebra Appl. 195(1993), 81–116.