<p>I am not sure how you measure distance between eigenspaces, but I do not think you can say anything non-trivial here without some assumption that the eigenvalues of $A$ are separated. For example, let $u$ and $v$ be two arbitrary unit vectors, and define $A = I + \varepsilon uu^\intercal$ and $B = I + \varepsilon vv^\intercal$. Then $(1-\varepsilon)B \preceq A \preceq (1+\varepsilon)B$. However, the leading eigenvector of $A$ is $u$ and the leading eigenvector of $B$ is $v$, and, since they were arbitrary, they can be as far apart as you want. </p>

CC BY-SA 3.0
2017-12-04T15:41:07.037Z
yes that makes sense. But if we look at this concrete example, it also seems that since $1$ gives a complete basis we could just add an $\epsilon$ fraction to all the basis vectors, i.e. distributing $uu^T$ and all the basis vectors would then still be close, in that case even less than $\epsilon$-close, or is that incorrect?
LeoW.
CC BY-SA 3.0
2017-12-04T16:39:16.383Z
I am not sure if I am getting your comment correctly. You could pick two arbitrary orthonormal bases $u_1, \ldots, u_n$ and $v_1, \ldots, v_n$, and distinct numbers $0 < \varepsilon_n <\ldots < \varepsilon_1 \le 1$, and define $A = I + \sum_{i = 1}^n{\varepsilon_i u_i u_i^T}$ and $B = I + \sum_{i = 1}^n{\varepsilon_i v_i v_i^T}$. $A$ and $B$ are still $(1+\varepsilon)$-close, but the unique eigenbasis of $A$ is $u_1, \ldots, u_n$, while the unique eigenbasis of $B$ is $v_1, \ldots, v_n$. Again, the two eigenbases are arbitrary and you can make them as far as you want, in whatever measure.
Sasho Nikolov
CC BY-SA 3.0
2017-12-04T16:43:01.907Z
Because of such examples, results that talk about stability of eigenvectors always need to assume that the eigenvalues are somehow separated.
Sasho Nikolov
CC BY-SA 3.0
2017-12-08T10:58:52.430Z
The ordering implies also that solving linear systems in the one operator is similar to the other one. Using the pseudo inverse this is similar to applying the inverse of the eigenvalues times the outer product of the eigenvectors. Hence is it correct to assume that even though the eigenspaces might be different, they ultimately will have a very close decomposition?
LeoW.
CC BY-SA 3.0
2017-12-09T06:26:28.493Z
I don't know what this means: "even though the eigenspaces might be different, they ultimately will have a very close decomposition".
Sasho Nikolov
CC BY-SA 3.0
2017-12-10T10:39:42.567Z
Apologies. Let me try to explain. So say we want to invert $A = \sum_i \lambda_i s_i s_i$. Then $A^{+} =\sum_{i: s_i \notin Null(A)} (1/\lambda_i) s_i s_i$. If we have the sparsifier $B = \sum_i  \sum_i \hat{\lambda}_i \hat s_i \hat s_i$ for $A$, then solving linear systems in each of these two matrices is almost equivalent (with an $\epsilon$-error). Applying the eigendecomposition for both this is $A^+b = \sum_i (\beta_i/\lambda_i) s_i$ and $B^+b = \sum_i (\hat{\beta}_i/ \hat{\lambda}_i) \hat s_i$. These must be equivalent and we know the $\lambda_i, \hat{\lambda}_i$ must be close.
LeoW.
CC BY-SA 3.0
2017-12-10T10:51:42.487Z
If we would apply this to an eigenvector of $A$, then this would be $(\beta_i/\lambda_i) s_i$ which would need to be very close to $\sum_i (\hat s_i^T s_i) (\hat{\beta}_i/\hat{\lambda}_i) \hat s_i$ for all eigenvectors $s_i$. But does this not imply that somehow there should be a decomposition of $\sum_i (1/\hat{\lambda}_i) \hat s_i \hat s_i^T$ which is quite similar to something like $\sum_i (1/\lambda_i + \epsilon) s_i s_i^T$? I am not sure whether I explained that well...
LeoW.
CC BY-SA 3.0
2017-12-10T20:24:52.660Z
I think I see what you are saying: of $A$ and $B$ spectrally approximate each other, and $u$ is an eigenvector of $B$ with eigenvalue $\lambda$, then $\| \lambda A^+  x - x\|  = \| A^+ B x - x\| \le \varepsilon \|x\|$, which can be seen as saying that $x$ is close to being an eigenvector of $A^+$ with eigenvalue $\frac1\lambda$. Maybe one can build some decomposition from this, but it would not be the spectral decomposition, as you can see from my answer
Sasho Nikolov
CC BY-SA 3.0
2017-12-11T21:05:39.330Z
Yes exactly. It would be interesting to see if this can be found efficiently!
LeoW.
CC BY-SA 3.0
2017-12-03T19:14:05.603Z
2017-12-03T19:14:05.603Z
Sasho Nikolov
<p>I am currently trying to understand whether I can make some claims about the relation between eigenspaces of a sparsifier and the original matrix. In this context, let me first define a couple of entities. </p>

<p><strong>Definition 1</strong>: Partial Ordering Among Matrices: 
We say that two commuting matrix $\mathbf A,\mathbf B$ have a partial ordering $\mathbf A \preceq \mathbf B$ if the matrix $\mathbf B - \mathbf A$ is positive semidefinite, i.e. $\vec x^T (\mathbf B - \mathbf A) \vec x \geq 0 $ for all non-zero $\vec x$.
Now with this definition we can define an $\epsilon$-approximation of the graph to be $(1- \epsilon) \mathbf B \preceq \mathbf A \preceq (1+\epsilon) \mathbf B$, i.e. $\mathbf B$ is an $\epsilon$-approximation of $\mathbf A$ (definitions vary here slightly). </p>

<p>Spielman and Peng famously gave the first algorithm to spectrally sparsify a graph, i.e. given a graph $G=(V,E)$, the algorithm returns a graph $H$ such that $H$ is an $\epsilon$ spectral approximation of $G$, with average degree $\mathcal{O}(1/\epsilon^2)$ (~ sparsity).
These spectral sparsifiers can then in turn be used to solve e.g. Laplacian systems in nearly linear time (nowadays I believe linear time was achieved by Joannis Koutis et al., or others around M. B. Cohen). </p>

<p>Now the question I have is the following:
Usually when comparing the solution of linear systems, instead of inverting the matrix, some sort or polynomial is used to approximate the inverse. Hence, the eigenspaces of the (pseudo-)inverse and the polynomial is the same and we can easily show that the eigenvalues of the polynomial and the inverse are all $\epsilon$-close. How does this change for a general case, wehere $\mathbf B$ is a spectral sparsifier of $\mathbf A$? Can I say anything about the relationship between eigenspaces? </p>

<p>My idea was to use the eigenvalue decomposition of both matrices and project the basis of $\mathbf B$ into the basis of $\mathbf A$. However this doesn't seem to give me a more qualitative understanding. Are there any ways to bound the differences eigenspaces? It seems that in the worst case the sum of plus and minus terms could cancel out each other allowing for quite large ranges of distances (from the projections) between the actual eigenvectors of $\mathbf A$ and $\mathbf B$?</p>

<na.numerical-analysis><sparse-matrix>
Graph sparsification and eigenspaces
LeoW.
# Graph sparsification and eigenspaces

(Asked by: username_0 on 2017-11-21)

I am currently trying to understand whether I can make some claims about the relation between eigenspaces of a sparsifier and the original matrix. In this context, let me first define a couple of entities.

**Definition 1**: Partial Ordering Among Matrices:
We say that two commuting matrix $\mathbf A,\mathbf B$ have a partial ordering $\mathbf A \preceq \mathbf B$ if the matrix $\mathbf B - \mathbf A$ is positive semidefinite, i.e. $\vec x^T (\mathbf B - \mathbf A) \vec x \geq 0 $ for all non-zero $\vec x$.
Now with this definition we can define an $\epsilon$-approximation of the graph to be $(1- \epsilon) \mathbf B \preceq \mathbf A \preceq (1+\epsilon) \mathbf B$, i.e. $\mathbf B$ is an $\epsilon$-approximation of $\mathbf A$ (definitions vary here slightly).

Spielman and Peng famously gave the first algorithm to spectrally sparsify a graph, i.e. given a graph $G=(V,E)$, the algorithm returns a graph $H$ such that $H$ is an $\epsilon$ spectral approximation of $G$, with average degree $\mathcal{O}(1/\epsilon^2)$ (~ sparsity).
These spectral sparsifiers can then in turn be used to solve e.g. Laplacian systems in nearly linear time (nowadays I believe linear time was achieved by Joannis Koutis et al., or others around M. B. Cohen).

Now the question I have is the following:
Usually when comparing the solution of linear systems, instead of inverting the matrix, some sort or polynomial is used to approximate the inverse. Hence, the eigenspaces of the (pseudo-)inverse and the polynomial is the same and we can easily show that the eigenvalues of the polynomial and the inverse are all $\epsilon$-close. How does this change for a general case, wehere $\mathbf B$ is a spectral sparsifier of $\mathbf A$? Can I say anything about the relationship between eigenspaces?

My idea was to use the eigenvalue decomposition of both matrices and project the basis of $\mathbf B$ into the basis of $\mathbf A$. However this doesn't seem to give me a more qualitative understanding. Are there any ways to bound the differences eigenspaces? It seems that in the worst case the sum of plus and minus terms could cancel out each other allowing for quite large ranges of distances (from the projections) between the actual eigenvectors of $\mathbf A$ and $\mathbf B$?

**Tags:** na.numerical-analysis, sparse-matrix

---

## 1 answers

### Answer by username_1 on 2017-12-03. Score: 0 | Accepted answer

I am not sure how you measure distance between eigenspaces, but I do not think you can say anything non-trivial here without some assumption that the eigenvalues of $A$ are separated. For example, let $u$ and $v$ be two arbitrary unit vectors, and define $A = I + \varepsilon uu^\intercal$ and $B = I + \varepsilon vv^\intercal$. Then $(1-\varepsilon)B \preceq A \preceq (1+\varepsilon)B$. However, the leading eigenvector of $A$ is $u$ and the leading eigenvector of $B$ is $v$, and, since they were arbitrary, they can be as far apart as you want.

> **Comments:**
> **username_0**: yes that makes sense. But if we look at this concrete example, it also seems that since $1$ gives a complete basis we could just add an $\epsilon$ fraction to all the basis vectors, i.e. distributing $uu^T$ and all the basis vectors would then still be close, in that case even less than $\epsilon$-close, or is that incorrect?  
> **username_1**: I am not sure if I am getting your comment correctly. You could pick two arbitrary orthonormal bases $u_1, \ldots, u_n$ and $v_1, \ldots, v_n$, and distinct numbers $0 < \varepsilon_n <\ldots < \varepsilon_1 \le 1$, and define $A = I + \sum_{i = 1}^n{\varepsilon_i u_i u_i^T}$ and $B = I + \sum_{i = 1}^n{\varepsilon_i v_i v_i^T}$. $A$ and $B$ are still $(1+\varepsilon)$-close, but the unique eigenbasis of $A$ is $u_1, \ldots, u_n$, while the unique eigenbasis of $B$ is $v_1, \ldots, v_n$. Again, the two eigenbases are arbitrary and you can make them as far as you want, in whatever measure.  
> **username_1**: Because of such examples, results that talk about stability of eigenvectors always need to assume that the eigenvalues are somehow separated.  
> **username_0**: The ordering implies also that solving linear systems in the one operator is similar to the other one. Using the pseudo inverse this is similar to applying the inverse of the eigenvalues times the outer product of the eigenvectors. Hence is it correct to assume that even though the eigenspaces might be different, they ultimately will have a very close decomposition?  
> **username_1**: I don't know what this means: "even though the eigenspaces might be different, they ultimately will have a very close decomposition".  
> **username_0**: Apologies. Let me try to explain. So say we want to invert $A = \sum_i \lambda_i s_i s_i$. Then $A^{+} =\sum_{i: s_i \notin Null(A)} (1/\lambda_i) s_i s_i$. If we have the sparsifier $B = \sum_i  \sum_i \hat{\lambda}_i \hat s_i \hat s_i$ for $A$, then solving linear systems in each of these two matrices is almost equivalent (with an $\epsilon$-error). Applying the eigendecomposition for both this is $A^+b = \sum_i (\beta_i/\lambda_i) s_i$ and $B^+b = \sum_i (\hat{\beta}_i/ \hat{\lambda}_i) \hat s_i$. These must be equivalent and we know the $\lambda_i, \hat{\lambda}_i$ must be close.  
> **username_0**: If we would apply this to an eigenvector of $A$, then this would be $(\beta_i/\lambda_i) s_i$ which would need to be very close to $\sum_i (\hat s_i^T s_i) (\hat{\beta}_i/\hat{\lambda}_i) \hat s_i$ for all eigenvectors $s_i$. But does this not imply that somehow there should be a decomposition of $\sum_i (1/\hat{\lambda}_i) \hat s_i \hat s_i^T$ which is quite similar to something like $\sum_i (1/\lambda_i + \epsilon) s_i s_i^T$? I am not sure whether I explained that well...  
> **username_1**: I think I see what you are saying: of $A$ and $B$ spectrally approximate each other, and $u$ is an eigenvector of $B$ with eigenvalue $\lambda$, then $\| \lambda A^+  x - x\|  = \| A^+ B x - x\| \le \varepsilon \|x\|$, which can be seen as saying that $x$ is close to being an eigenvector of $A^+$ with eigenvalue $\frac1\lambda$. Maybe one can build some decomposition from this, but it would not be the spectral decomposition, as you can see from my answer  
> **username_0**: Yes exactly. It would be interesting to see if this can be found efficiently!  

---

