10
$\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$
  • $\begingroup$ Is the psd property crucial? $\endgroup$ – Felix Goldberg Sep 8 '14 at 15:07
  • $\begingroup$ There is a large body of work on this problem for stochastic matrices. Is this relevant to your setup? $\endgroup$ – Felix Goldberg Sep 8 '14 at 15:28
  • $\begingroup$ @FelixGoldberg - My particular application concerns PSD matrices, but perhaps you can link to a survey or something? $\endgroup$ – Dustin G. Mixon Sep 9 '14 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$ – Felix Goldberg Sep 9 '14 at 8:51
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\|$.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Felix Goldberg Sep 10 '14 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$ – Terry Loring Sep 10 '14 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\|}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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