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$ 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$ 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$ 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$ 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$ 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$ 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.