<p>Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?</p>

<p>Are there any families of Laplacians for which it takes almost linear time?</p>

CC BY-SA 3.0
2011-10-30T21:45:58.770Z
does linear time mean $O(n^2)$ or $O(m)$ ($m$ being the number of edges in the graph)  ?
Suresh Venkat
CC BY-SA 3.0
2011-10-30T22:57:02.670Z
I think $O(m)$ is more appropriate since -to the best of my understanding- $O(n^2)$ is the cost of a principal eigenvector for a "generic" $n\times n$ matrix. If we assumed O(n^2) to be linear I think that it would imply the answer "all Laplacians" to the second question. I am not sure though.
Dimitris
CC BY-SA 3.0
2011-11-04T19:27:40.467Z
Are you interested in exact or approximate solutions? Btw, what is the reference for the O(n^2) solution you mention? For approximate solutions, there are the Lanczos/power methods that run in near-linear time (I think).
Alex Andoni
CC BY-SA 3.0
2011-11-04T23:28:45.250Z
Either exact or approximate within $\epsilon$ is fine. I think that the power method is $O(n^2)$ modulo the approximation error: ${\bf L}^i{\bf x}$ costs O(n^2) per iteration, and the number of iterations to approach the optimal solution within $\epsilon$ is a function of the two largest eigenvalues. I might be missing something. Do you have a references for the near-linear time?
Dimitris
CC BY-SA 3.0
2011-11-05T18:32:44.890Z
A standard reference seems to be: "J. Kuczynski and H. Wozniakowski. Estimating the largest eigenvalues by the power
and Lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applications, 13:1094–1122, 1992." It obtains $1+\epsilon$ approximation in $O(1/\epsilon\cdot m\cdot \log n)$ time (essentially, note that an iteration of the power method runs in $O(m)$ time). The approximation means to find a vector $x$ s.t. $x^tLx\ge (1-\epsilon)\lambda_1\|x\|^2$. If the eigenvalues drop sufficiently rapidly, then one can get even better estimates.
Alex Andoni
CC BY-SA 3.0
2011-11-06T04:52:48.523Z
I understand that if $m$ is nearly linear then the power method will be nearly linear in $n$. In the general case, where one would expect $m=n^2$, is there any method that possibly "exploits" the properties of the (non-sparse) Laplacian to run faster?
Dimitris
CC BY-SA 3.0
2011-11-06T04:57:22.527Z
On a parallel note, I was wondering if the graph sparsification tools of Spielman and Teng can be used here. If  one can sparsify Laplacians in a way that the eigenspaces are preserved, then the power method would run in nearly linear time on the sparsifier. Assuming that the "sparsified" eigenspaces are close to the original ones, the power method would output an approximate yet linear-time (in $n$) computable eigenvector for the initial Laplacian.
Dimitris
CC BY-SA 3.0
2011-11-07T19:09:20.693Z
Good question -- this is quite conceivable. As you say, one could use spectral sparsification to the graph first, which approximately preserves the eigenvectors, and then work on a sparse graph. However, the algorithms for computing the spectral sparsification are less efficient than the direct eigenvector computation methods (to the best of my knowledge). But this is certainly an active research area so things may change :) At the same time, Spielman and Teng do show how to compute the Fiedler's vector more efficiently.
Alex Andoni
<linear-algebra><matrices><sparse-matrix><compressed-sensing><linear-equations>
Complexity of finding the leading eigenvector of a graph Laplacian
Dimitris
# Complexity of finding the leading eigenvector of a graph Laplacian

(Asked by: username_0 on 2011-10-30)

Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?

Are there any families of Laplacians for which it takes almost linear time?

**Tags:** linear-algebra, matrices, sparse-matrix, compressed-sensing, linear-equations

> **Comments:**
> **username_1**: does linear time mean $O(n^2)$ or $O(m)$ ($m$ being the number of edges in the graph)  ?  
> **username_0**: I think $O(m)$ is more appropriate since -to the best of my understanding- $O(n^2)$ is the cost of a principal eigenvector for a "generic" $n\times n$ matrix. If we assumed O(n^2) to be linear I think that it would imply the answer "all Laplacians" to the second question. I am not sure though.  
> **username_2**: Are you interested in exact or approximate solutions? Btw, what is the reference for the O(n^2) solution you mention? For approximate solutions, there are the Lanczos/power methods that run in near-linear time (I think).  
> **username_0**: Either exact or approximate within $\epsilon$ is fine. I think that the power method is $O(n^2)$ modulo the approximation error: ${\bf L}^i{\bf x}$ costs O(n^2) per iteration, and the number of iterations to approach the optimal solution within $\epsilon$ is a function of the two largest eigenvalues. I might be missing something. Do you have a references for the near-linear time?  
> **username_2**: A standard reference seems to be: "J. Kuczynski and H. Wozniakowski. Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applications, 13:1094–1122, 1992." It obtains $1+\epsilon$ approximation in $O(1/\epsilon\cdot m\cdot \log n)$ time (essentially, note that an iteration of the power method runs in $O(m)$ time). The approximation means to find a vector $x$ s.t. $x^tLx\ge (1-\epsilon)\lambda_1\|x\|^2$. If the eigenvalues drop sufficiently rapidly, then one can get even better estimates.  
> **username_0**: I understand that if $m$ is nearly linear then the power method will be nearly linear in $n$. In the general case, where one would expect $m=n^2$, is there any method that possibly "exploits" the properties of the (non-sparse) Laplacian to run faster?  
> **username_0**: On a parallel note, I was wondering if the graph sparsification tools of Spielman and Teng can be used here. If  one can sparsify Laplacians in a way that the eigenspaces are preserved, then the power method would run in nearly linear time on the sparsifier. Assuming that the "sparsified" eigenspaces are close to the original ones, the power method would output an approximate yet linear-time (in $n$) computable eigenvector for the initial Laplacian.  
> **username_2**: Good question -- this is quite conceivable. As you say, one could use spectral sparsification to the graph first, which approximately preserves the eigenvectors, and then work on a sparse graph. However, the algorithms for computing the spectral sparsification are less efficient than the direct eigenvector computation methods (to the best of my knowledge). But this is certainly an active research area so things may change :) At the same time, Spielman and Teng do show how to compute the Fiedler's vector more efficiently.  

---

## 0 answers

