# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## Appendix C Proof of Theorem 2  
First, we prove the the existence of the approximation guarantee. Let us consider the result [57]  
\[nW_{1}(\lambda,\tilde{\lambda})\leq 2\mathcal{G}\Delta\tilde{\mathcal{G}}, \tag{10}\]  
for the earth mover distance between the spectrum of \(\mathcal{G}\) and \(\tilde{\mathcal{G}}\). This implies that the approximation error is bounded by the edit distance between the original graph, \(\mathcal{G}\), and the graph used to compute the approximate spectrum, \(\tilde{\mathcal{G}}\). The decomposition employed in Algorithm 1, with depth \(d\), applied to graphs in \(\mathcal{S}_{1/2}\), obtains a surrogate graph \(\tilde{\mathcal{G}}\) where  
\[ \begin{array}{rcl}\mathcal{G}\Delta\tilde{\mathcal{G}}&=&\alpha n^{1/2}+2 \alpha\sqrt{n/2}+\cdots+2^{(d-1)}\alpha\sqrt{n/2^{(d-1)}}\\ &=&\alpha n^{1/2}\sum\limits_{i=0}^{d-1}\sqrt{2}^{i}\\ &=&\alpha n^{1/2}(1+\sqrt{2})(2^{\frac{d}{2}}-1)\\ &=&\mathcal{O}(n^{1/2}\sqrt{2}^{d}-n^{1/2}),\end{array}  \tag{11}\]  
edges have been removed from the original graph \(\mathcal{G}\). Here, we have kept the second term in the big-O notation to provide an expression for zero error when \(d=0\), i.e., if the original graph is considered, the true spectrum must be computed. A vanishing error for sufficiently large graphs, i.e.,  
\[\lim_{n\to\infty}W_{1}(\lambda,\tilde{\lambda})\leq\lim_{n\to\infty}\frac{2 \mathcal{G}\Delta\tilde{\mathcal{G}}}{n}=0, \tag{12}\]  
implies that the number of removed edges meets \(\mathcal{G}\Delta\tilde{\mathcal{G}}=o(n)\). This ensures that (12) becomes zero asymptotically. Here, \(o(\cdot)\) is used to denote _little-o notation_, i.e., \(f(x)=o(g(x))\) implies \(\lim\limits_{x\to\infty}f(x)/g(x)=0\) as \(g(x)\) is nonzero, or becomes nonzero after certain point. Therefore, to guarantee this condition we should show that \(\mathcal{G}\Delta\tilde{\mathcal{G}}\in\mathcal{O}(n^{(1-\delta)})\) for some \(\delta\in\mathbb{R}_{++}\). If we set the depth of the decomposition to \(d^{*}=\mathcal{O}(\eta_{\delta}\log n)\) as stated in the theorem, the number of removed edges given by (A2) becomes  
\[ \begin{array}{rcl}\mathcal{G}\Delta\mathcal{G}&=&\mathcal{O}(n^{1/2}\sqrt{2} ^{d^{*}}-n^{1/2})\\ &=&\mathcal{O}(n^{1/2}\cdot n^{\eta_{\delta}}-n^{1/2})\\ &=&\mathcal{O}(n^{1-\delta}-n^{1/2})\\ &\in&\mathcal{O}(n^{1-\delta}),\end{array}  \tag{10}\]  
as we wanted. Here, we have used the definition \(\eta_{\delta}\triangleq 1-2\delta\). Using this result, we can show that the approximation error when employing the proposed decomposition with depth \(d^{*}\) is  
\[W_{1}(\lambda,\tilde{\lambda}) \leq 2\frac{\mathcal{G}\Delta\mathcal{G}}{n} \tag{11}\] \[= \mathcal{O}(1/n^{\delta}-n^{1/2})\] \[\in \mathcal{O}(1/n^{\delta}),\]  
where \(\delta\) it is seen to define the rate of decay of the error. From the definition of \(d^{*}\) it is observed that for \(0\leq\delta<1/2\) the depth parameter is positive, which implies a feasible decomposition attaining an \(\mathcal{O}(1/n^{\delta})\)-approximation as desired. For \(\delta=1/2\) we have \(d=0\) which implies that no decomposition is performed and the original graph, \(\mathcal{G}\), is used to compute the spectrum. In this case, it is seen from expression (11) that the error is zero. The time complexity can be obtained by considering the dominant (competing) operations: (i) computation of eigendecomposition of the leaves, and (ii) computation of the graph decomposition. The complexity for (i), \(T_{e}(n,d)\), is obtained by considering that there are \(2^{d}\) leaves in the decomposition and that each leaf contains a \(n/2^{d}\times n/2^{d}\) matrix, i.e.,  
\[T_{e}(n,d)=\mathcal{O}(2^{d}T_{f}(n/2^{d})), \tag{12}\]  
where \(T_{f}(m)\) is the time required by \(f(\cdot)\) to compute the eigendecomposition of an \(m\times m\) matrix.