# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 1 Introduction  
Graphs, as combinatorial objects, are important in many disciplines. They allow us to capture complex interactions between different entities (elements). Due to this ability, they have found applications in a plethora of fields, spanning from biology to psychology, and from logistics to medical sciences. Additionally, interest has emerged in adapting classical signal processing methods to deal with signals in irregular domains, e.g., signals defined on graphs [1, 2]. As for traditional signal processing, the fundamental tool of graph signal processing is its analogous Fourier transform: the so-called _graph Fourier transform_ (GFT). This transform interprets a signal on a graph through its graph _modes_. The concept of graph modes can be understood by considering the Laplacian matrix of a graph as a discrete representation of a manifold. The so-called graph modes are then the discrete counterpart of eigenfunctions of the Laplacian operator over the continuous manifold. Therefore, the graph modes can can be identified as the eigenvectors of the Laplacian matrix and can be obtained through its eigendecomposition. Here, we remark that although the analogy connecting with manifolds employs the Laplacian, the concept of GFT holds for different matrix representations of the graph such as the adjacencymatrix or normalized Laplacian [3]. For instance, let us consider an undirected (possibly weighted) graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) defined on \(n\) vertices with vertex set \(\mathcal{V}=\{v_{1},v_{2},\ldots\}\) and edge set \(\mathcal{E}\) and let \(\mathbf{A}\) and \(\mathbf{D}=\text{diag}(\mathbf{A1})\) be its (weighted) adjacency and degree matrices, respectively. Here, \([\mathbf{A}]_{i,j}>0\) only if \((v_{i},v_{j})\in\mathcal{E}\). Then, selecting a matrix representation of the graph, \(\mathbf{S}\), e.g., Laplacian, normalized Laplacian, adjacency matrix, we can define the graph Fourier transform of an \(n\)-dimensional signal \(\mathbf{x}\) over \(\mathcal{G}\) as [3]  
\[\mathbf{x}_{\text{f}}=\mathbf{U}^{T}\mathbf{x}, \tag{1}\]  
where \(\mathbf{U}\) is the orthogonal eigenvector matrix or the so-called _graph modes_ obtained from the eigendecomposition of \(\mathbf{S}\), i.e., \(\mathbf{S}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}\), and \(\mathbf{\Lambda}\) is the diagonal matrix of eigenvalues, \(\lambda~{}=~{}\{\lambda_{1},\ldots,\lambda_{n}\}\) also known as _graph frequencies_. Although there are several alternatives to select the matrix \(\mathbf{S}\), we follow the formalism of [4] and use the eigenvalues of the normalized Laplacian, i.e., \(\mathbf{L}_{\text{n}}:=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), to define the spectrum of \(\mathcal{G}\) throughout this paper. Thus, the graph modes are then defined as the eigenvectors of \(\mathbf{L}_{\text{n}}\). We make this consideration here as the normalized graph Laplacian's eigenvectors define generalized translation and modulation operators, see, e.g., [3], and its spectrum relates well with graph invariants because its definition is consistent with those of eigenvalues in spectral geometry and stochastic processes [4], which is not the case for the spectrum of other choices of \(\mathbf{S}\). As noted in [5], one of the main issues of performing the GFT is that a full eigendecomposition is required. This naturally incurs a \(\mathcal{O}(n^{3})\) cost, which for many applications is undesirable or even infeasible. Therefore, before aiming to achieve a complexity comparable to the fast Fourier transform (FFT), we require to obtain a better understanding of the eigendecomposition of \(\mathbf{L}_{\text{n}}\). In this context, a series of research works propose approximate fast GFT methods [5; 6; 7]. These methods employ Givens rotations and truncated Jacobi iterations to compute an orthogonal basis that approximately diagonalizes the matrix representation of the graph [8].