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.

  • 3
    Ah, the old "it follows immediately" trick.2012-12-27
  • 3
    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.2012-12-27
  • 0
    @user1551 For matrices with positive entries the leading eigenvector has positive entries; this eliminates the sign ambiguity.2012-12-29

1 Answers 1