11
$\begingroup$

Suppose I have a symmetric positive semidefinite matrix $A$ with leading eigenvalue $1$ of multiplicity $1$ and remaining eigenvalues $\leq\epsilon$. I am told that another symmetric positive semidefinite matrix $B$ is close in some sense to $A$. I wish to conclude that the leading eigenvector of $B$ is therefore close in some sense to that of $A$.

Question: What notions of closeness correspond to existing theorems of this sort?

One solution: Let $a$ and $b$ denote leading eigenvectors of $d\times d$ matrices $A$ and $B$, respectively, scaled so that $\|a\|_2^2=1$ and $\|b\|_2^2$ is the leading eigenvalue of $B$. Then by triangle, Eckart–Young–Mirsky, and triangle again, we have

$$\|bb^\top-aa^\top\|_F\leq\|bb^\top-B\|_F+\|B-aa^\top\|_F\leq2\|B-aa^\top\|_F\leq2\big(\|B-A\|_F+\|A-aa^\top\|_F\big)\leq2\|B-A\|_F+2\sqrt{d-1}\epsilon.$$

For this attempt, I don't like the additive loss in $\epsilon$, and I doubt it's necessary. Can I get better performance with a different norm? Perhaps the spectral norm?

$\endgroup$
4
  • $\begingroup$ Is the psd property crucial? $\endgroup$ Commented Sep 8, 2014 at 15:07
  • $\begingroup$ There is a large body of work on this problem for stochastic matrices. Is this relevant to your setup? $\endgroup$ Commented Sep 8, 2014 at 15:28
  • $\begingroup$ @FelixGoldberg - My particular application concerns PSD matrices, but perhaps you can link to a survey or something? $\endgroup$ Commented Sep 9, 2014 at 0:22
  • $\begingroup$ A neat overview is given in the 2001 paper by Cho and Meyer sciencedirect.com/science/article/pii/S0024379501003202 There's also newer work of course, that sharpens the constants etc. $\endgroup$ Commented Sep 9, 2014 at 8:51

2 Answers 2

7
$\begingroup$

You can get a nice estimate using the spectral norm.

Theorem 3.2.32 of Bratteli and Robinson vol. 1 tell us an estimate on $f(A) - f(B)$ for a variety of functions. Take $f:\mathbb R \rightarrow \mathbb R$ to be zero on $(-\infty, \epsilon]$ and one on $[1,\infty)$, interpolating with some quadratics. I think you get $$ \|f(A) - f(B)\| \leq \frac{2\|A - B\|}{1-\epsilon} $$ and this helps. Notice $f(A) = aa^*$ and $f(B) = bb^*$ and I assume you used transpose because you assumed real scalars. Works either way, I think.

I should add I am not entirely sure of the constant, just that the bound in linear in $\|A - B\|$.

$\endgroup$
2
  • $\begingroup$ Are you sure you have the right reference? I have the book in front of me now and the Theorem 3.2.32 (on page 239) seems to be about something else. $\endgroup$ Commented Sep 10, 2014 at 13:58
  • $\begingroup$ I don't have the book out of the library, so can't check. It should be a result about derivations and norms and functional calculus. A 2-by-2 matrix trick turns $f(A) - f(B)$ problems to commutator problems. $\endgroup$ Commented Sep 10, 2014 at 15:01
4
$\begingroup$

The spectral projection of $A$ for eigenvalue $1$ can be realized as $P_A = \dfrac{1}{2\pi i} \oint_{\Gamma} (z I - A)^{-1} \; dz$ where $\Gamma$ is a contour that encloses $1$ but none of the other eigenvalues. In particular, take $\Gamma$ to be a circle of radius $r$ centred at $1$, where $r = (1-\epsilon)/2$. For $z \in \Gamma$ we have (using the $\ell^2$ operator norm) $\|(z I - A)^{-1}\| \le 1/r$. Then if $\|B - A\| < r$, $z I - B$ is invertible for $z \in \Gamma$, with $$\|(z I - B)^{-1} - (zI-A)^{-1} \| \le \dfrac{\|(z I - A)^{-1}\|^2 \|B-A\|}{1 - \|B - A\| \|(zI - A)^{-1}\|} \le \dfrac{\|B-A\|}{r(r - \|B-A\|)}$$ and $P_B = \dfrac{1}{2\pi i} \oint_{\Gamma} (z I - B)^{-1} \; dz$ is a spectral projection of rank $1$ with $\|P_B - P_A\| \le \dfrac{\|B-A\|}{r - \|B-A\|}$.

$\endgroup$

You must log in to answer this question.

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