3
$\begingroup$

For a matrix $A$ let $\|A\|$ be the norm given by $\|A\|=\sup_{v \neq 0}\frac{\|Av\|}{\|v\|}$ where $\|v\|$ is the Euclidian norm on the vector $v$.

Suppose we have matrices $M$ and $S$ with leading eigenvectors $u$ and $\hat{u}$ respectively. If we have $\|M-S\| \leq \theta\|M\|$ does this imply $\|\hat{u}-u\|\leq 2\theta$, and if so, how?

This comes from the paragraph containing equation (1) on page 2 of this paper http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf but I don't see how the result is "immediate" as they claim.

In response to user1551, $M$ is an $n \times n$ symmetric matrix, $u$ is "the" eigenvector of $M$ corresponding to the eigenvalue of largest magnitude.

$S$ is some sparsification of $M$ obtained by setting each entry of $M$ to $0$ independently with probability $1-p$ then rescaling non-zero entries by $1/p$.

$\hat{u}$ is "the leading eigenvector" of $S$.

Let's assume the entries of $M$ are all positive, then by Perron-Frobenius say that $u$ and $\hat{u}$ are non-negative unit eigenvectors, if that makes it easier.

$\endgroup$
3
  • 3
    $\begingroup$ Ah, the old "it follows immediately" trick. $\endgroup$
    – Alexander Gruber ♦
    Dec 27, 2012 at 5:09
  • 3
    $\begingroup$ Please elaborate more on the definitions of $M$ and $S$. For non-specialists like me, the descriptions of the two matrices in the paper are too vague. That how the eigenvectors are chosen is also unclear. For instance, if $u$ is an eigenvector, so is $ku$ for all $k\not=0$. So, does the cited paper claim that $\|k_1\hat{u}+k_2u\|\le2\theta$ for any $k_1,k_2\not=0$? Even if we take unit eigenvectors, the statement that $\|\hat{u}\pm u\|\le2\theta$ (if $u$ is an eigenvector, so is $-u$) is not true in general. $\endgroup$
    – user1551
    Dec 27, 2012 at 7:27
  • $\begingroup$ @user1551 For matrices with positive entries the leading eigenvector has positive entries; this eliminates the sign ambiguity. $\endgroup$
    – user53153
    Dec 29, 2012 at 8:09

1 Answer 1

Reset to default
3
$\begingroup$

I don't believe such a strong stability result. Consider the matrix $$M=\begin{pmatrix} 1.01 & 0.01 \\ 0.01 & 1 \end{pmatrix}$$ According to WolframAlpha, its leading eigenvector, normalized to unit length, is $u\approx (0.85, 0.525)^T$.

We don't need to be gurus of sparse computing to find $$S=\begin{pmatrix} 1.01 & 0 \\ 0 & 1 \end{pmatrix}$$ (up to irrelevant scaling). The leading eigenvector is obviously $\widehat u=(1,0)^T$.

In conclusion, $\|M-S\|\le 0.01\|M\|$ but $\|u-\widehat u\| > 0.5$.

I hear that the book The Algebraic Eigenvalue Problem by Wilkinson is where stability results of this kind are found. I never read the book myself, though.

$\endgroup$
6
  • $\begingroup$ This example doesn't work. By the OP's explanation on the construction of $S$, $S$ is either the zero matrix (when $p=1$) or it is scaled by a factor larger than $1$ (when $p<1$) after setting some entries of $M$ to zero. $\endgroup$
    – user1551
    Dec 29, 2012 at 8:15
  • $\begingroup$ But apparently your example can be modified to work, though. So +1. $\endgroup$
    – user1551
    Dec 29, 2012 at 8:18
  • $\begingroup$ @user1551 Scaling does not affect eigenvectors, as my parenthetical remark indicated. $\endgroup$
    – user53153
    Dec 29, 2012 at 8:19
  • $\begingroup$ Yes, but scaling would affect $\|M-S\|$. So you need a continuity argument to fill the loophole. $\endgroup$
    – user1551
    Dec 29, 2012 at 8:21
  • $\begingroup$ @user1551 Valid point. However, the purpose of scaling is to bring $S$ closer to $M$, not to make it more different. (The goal of sparsification is to produce a sparse matrix that is close to the original one). If keeping the size of errors much less than $1$ wasn't important, we could just say that $\|u-\widehat u\|\le 2$ and save ourselves a lot of time. $\endgroup$
    – user53153
    Dec 29, 2012 at 8:38

You must log in to answer this question.

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