# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 5 Divide-And-Conquer for Fast Graph Spectrum Estimation
### Eigenvectors Computation  
Although we have mainly focused on the computation of the spectrum of the graph, for the sake of completeness, in the following, we present some theoretical results that provide insights on the approximation quality of the graph eigenvectors. These results motivate the later discussion of the landscape for the approximation of graph filters in Section 7.  
To bound the error of the eigenvectors obtained through the proposed decomposition, we make use of the Bauer-Fike theorem [PERSON] and [PERSON] (1971) and provide the following result.  
**Theorem 3**.: _Let \(\mathbf{S}\) be the matrix representation of graph \(\mathcal{G}\). Further consider \(\mathbf{\hat{S}}\) as the matrix representation of the graph \(\mathcal{H}\) obtained from \(\mathcal{G}\) at depth \(d\). If \(\mathbf{\hat{u}}\) is the eigenvector of \(\mathbf{\hat{S}}\) with eigenvalue \(\hat{\mu}\), then there exists an eigenvector \(\mathbf{u}\) of \(\mathbf{S}\), with eigenvalue \(\mu\), such that_  
\[\frac{1}{n}\|\mathbf{\hat{u}}-\mathbf{u}\|_{2}^{2}\leq\frac{4\gamma}{\min_{l\in\mathrm{ eig}(\mathbf{S}),l\
eq\mu}|l-\mu|^{2}}. \tag{4}\]  
_where \(\gamma:=\frac{1}{n}\|\mathbf{S}-\mathbf{\hat{S}}\|_{\mathrm{F}}^{2}\)._  
Proof.: See Appendix D.  
Despite that the above result shows a vanishing behavior in the normalized Euclidean distance between the approximated and true eigenvectors if \(\gamma\in o(n)\), it also shows that for highly clustered eigenvalues, the approximation error can be large. This result is not surprising as all eigendecomposition methods present difficulties for defining the eigenspace of highly clustered eigenvalues.  
A possible way to improve the approximation error for the eigenvectors is through iterative refinement. Here, we will use the inverse iteration method to show that it is possible to perform improvements in near-linear time. The result is presented in the following theorem.  
**Theorem 4**.: _Let \((\hat{\mu},\,\hat{\mathbf{u}})\) be an \(\mathcal{O}(1/n^{\delta})\)-approximated eigenpair of the matrix representation, \(\mathbf{S}\), of a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) with \(m\) edges. Then, the kth iteration of the inverse iteration method, i.e.,_  
\[\mathbf{\hat{u}}_{k+1}=\frac{1}{c_{k}}(\mathbf{S}-\hat{\mu}\mathbf{I})^{-1}\mathbf{\hat{u}}_{ k}, \tag{5}\]  
_where the normalization constant \(c_{k}\) is appropriately chosen, produces an eigenvector estimate \(\mathbf{\hat{u}}_{k+1}\) such that_  
\[\|\mathbf{u}-\mathbf{\hat{u}}_{k+1}\|_{2}\in\mathcal{O}\bigg{(}\bigg{|}\frac{1/n^{ \delta}}{\mu-\mu_{\mathrm{close}}}\bigg{|}^{k}\bigg{)}, \tag{6}\]  
_where \(\mu\) is the closest eigenvalue of \(\mathbf{S}\) to \(\hat{\mu}\) and \(\mu_{\mathrm{close}}\) is the closest eigenvalue of \(\mathbf{S}\) to \(\lambda\). Moreover, such an \(\mathbf{\hat{u}}_{k+1}\) can be computed in expected time \(\tilde{\mathcal{O}}(m\log^{2}n\log 1/\eta)\) at \(\eta\)-accuracy when \(\mathbf{S}\) is the combinatorial Laplacian. For cases where \(\mathbf{S}\) is the graph adjacency matrix, the complexity result holds for eigenpairs with \(\hat{\mu}\geq\max_{v\in\mathcal{V}}\mathrm{deg}(v)\)._  
Proof.: See Appendix E.  
Although the proposed improvement of the approximation quality of the eigenvectors is based on an iterative method, the inverse iteration method tends to convergence in few iterations (typically one) when the approximate eigenvalue is close to the true one. Finally, we stress that the previous result is not the tightest in terms of computational complexity. If further structure of the Laplacian is known, e.g., planarity, faster solvers [32] can be employed to speed up the computation of the inverse iteration method. Notice that although the power method could have been used to compute the modes of the graph, having available \(\mathcal{O}(1/n^{\delta})\)-approximations for all eigenvalues leads to an overall reduction of the computational effort.