# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 7 Approximation of Graph Filtering
### A Note on Graph Filter Bank Design  
Motivated by the current developments in graph filtering [39; 40; 41; 42; 43], there has been a large effort in defining (and designing) filter banks for the task of filtering signals in graphs [17; 44; 45]. Although there are many alternatives for designing filter banks in general, as remarked in [46], a guiding principle when designing filter banks is to identify gaps in the spectrum of the matrix representation of the graph, e.g., normalized Laplacian or adjacency matrix. For identifying such gaps one requires to have access  
Figure 8: Approximation error for graph filtering using the proposed hierarchical decomposition for different kinds of inputs. (**a**) Comparison of the approximation error for graph with varying number of nodes and filter order \(K=30\). Comparison of the approximation error for different filter orders for (**b**) Gaussian and bipolar signals and (**c**) positive and unipolar signals.  
either to the full spectrum, which for large-size graphs might not be feasible. Therefore, an approximation method for identifying gaps in the spectrum of such matrices is required.  
Here, is where our method provides an approximate solution for designing graph filter banks. In this sense, there are two possible ways to use the proposed method. The first is merely a direct application of our results and estimates the spectrum of the graph by means of the introduced hierarchical decomposition. The second consists of estimating the cumulative spectral density function of the graph [c.f Equation (7)].  
For approximating such a function, a widely used method is the _kernel polynomial method_ (KPM) [47]. This method has been adapted in [46] using a stochastic estimator of the trace of a matrix which incurs an overall complexity of \(\mathcal{O}(KJ|\mathcal{E}|)\), where \(K\) and \(J\) are the order of the filters used for approximating the Heaviside function and the number of random samples required by the method, respectively. For non-sparse graphs, i.e., \(|\mathcal{E}|=\Omega(n)\), this approach might not be appealing as its complexity is not linear anymore in the size of the graph and the number of random samples required by [PERSON]'s method for estimating \(\operatorname{tr}(\mathbf{A})\), for any given matrix \(\mathbf{A}\), is known to require \(J~{}=~{}6e^{-2}\ln(\frac{2}{g}\text{rank}\{\mathbf{A}\})\) samples for an error of at most \(\epsilon\) with probability \(\delta\) when Rademacher distributed vectors are employed [48]. Hence, in such cases, the hierarchical decomposition, with deterministic bounds, could be used as an alternative to compute a fast approximation for the cumulative spectral density of the matrix representation of the graph. In this case, using the result of Theorem 2, we can guarantee that our approximation to the cumulative spectral density is asymptotically efficient (for increasing graph sizes) and is related to the edit graph distance. Further, differently from the KPM, our method provides not only an approximation for the CDF but to both eigenvalues and eigenvectors. And if desired, the KPM can be instead employed in the leaves of the decomposition to approximate the CDF at them and then later on construct the global CDF of the graph. This last modification could lead to a significant reduction as the full eigendecomposition of the submatrices at the leaves is no longer required.