1
$\begingroup$

I have become confused on some basic questions concerning the perturbation theory of the generalized eigenvalue problem. I am likely missing something simple, but I have a couple of questions about the literature on this subject.


Consider the generalized eigenvalue problem $Ax = \lambda Bx$ for $n$-square Hermitian matrices $A$ and $B$. The Crawford number is defined to be

$$ c(A,B) := \inf_{x\in \mathbb{C}^n, \|x\|_2=1} |x^*(A+iB)x|. $$

Assume $c(A,B) > 0$, which ensures that there exists $Q$ such that $Q^*AQ$ and $Q^*BQ$ are simultaneous diagonalized, the generalized eigenvalues $\lambda$ being the ratio of these diagonal entries. For each generalized eigenvalue $\lambda_i$ with eigenvector $q_i$, the associated angle is defined to be the angle between a fixed ray and the complex number $\theta_i = q_i^*Aq_i + iq_i^*Bq_i$.

I am interested in perturbed versions of this problem, namely $(A+E)x = \lambda (B+F)x$ where $\|E\|_{\rm op}^2 + \|F\|_{\rm op}^2 =: \epsilon < c(A,B)$. Here, $\|E\|_{\rm op}$ is the spectral (operator 2-) norm. Stewart (1979, Theorem 3.2) derives the result

$$ |\theta_i - \tilde{\theta}_i|\le \arcsin\left( \frac{\epsilon}{c(A,B)} \right) =: \mathrm{RHS}_1. $$

Here, $\tilde{\theta}_i$ are the angles associated with the eigenvalues of the perturbed problem. In Golub and Van Loan (2012, Theorem 8.7.3), they cite Stewart (1979) as saying

$$ | \arctan(\lambda_i) - \arctan(\tilde{\lambda_i})| \le \arctan\left( \frac{\epsilon}{c(A,B)} \right) =: \mathrm{RHS}_3. $$

I believe it's the case that $| \arctan(\lambda_i) - \arctan(\tilde{\lambda_i})| = |\theta_i - \tilde{\theta}_i|$, which would make the result of Golub and Van Loan (2012) a strict strengthening of the result from Stewart (1979) since $\mathrm{RHS}_3 \le \mathrm{RHS}_1$.

In deriving his result, Stewart reduces his problem to an elementary question of geometry. By my reading, this problem is as follows: given a circle $C_1$ with radius $c(A,B)$ and another circle $C_2$ centered at a point on $C_1$ with radius $\epsilon$, what is the angle of the arc between the center of $C_2$ and an intersection point of $C_1$ and $C_2$. Stewart states the solution of this problem is $\mathrm{RHS}_1$, but my derivation is that the solution to this problem is actually $\mathrm{RHS}_2 := 2\arcsin(\epsilon/(2c(A,B))$.

For the relevent region $0 < \epsilon < c(A,B)$, $\mathrm{RHS}_1 \ge \mathrm{RHS}_2 \ge \mathrm{RHS}_3$. Here are my two questions:

  • Am I correct that Stewart (1979)'s analysis actually leads to the stronger bound $\mathrm{RHS}_2$ for the left-hand side?
  • Is the bound $\mathrm{RHS}_3$ correct, and if so, where is a correct proof? Is it contained in Stewart (1979)?

Any references would be great. I am aware the monograph by Stewart and Sun contains a discussion of this problem, but I do not have access to a copy of this book right now.

$\endgroup$

1 Answer 1

0
$\begingroup$

After some more contemplation and reading, I have gone a long way towards answering my own question.

My purported improved bound $\mathrm{RHS}_2$ is incorrect (at least for the reasons I believed it) because I misinterpreted the geometry problem. The problem is actually

Given a circle $C_1$ with radius $c(A,B)$ and another circle $C_2$ centered at a point on $C_1$ with radius $\epsilon$, what is the maximum angle between the center of $C_2$, the center of $C_1$, and a point on $C_2$.

In this case, the maximizer is when the triangle described by this angle is a right triangle with hypotenuse $c(A,B)$ and opposite leg $\epsilon$. This gives the bound $\mathrm{RHS}_1 = \arcsin(\epsilon/c(A,B))$ as claimed by Stewart.

Now having gotten my hands on Matrix Perturbation Theory and done more reading, I have not seen the $\mathrm{RHS}_3$ bound anywhere in the literature except for Golub and Van Loan, which cite Stewart 1979 for a proof which (unless I'm really missing something) it does not contain.

I am now reasonably convinced $\mathrm{RHS}_1$ is the best possible bound for this problem of this flavor only depending on $\epsilon$ and $c(A,B)$. (There are certainly stronger bounds, such as those by Sun (1982) and Mathias and Li (2004), but they use different parameters than $\epsilon$ and $c(A,B)$.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .