Approximate fast graph Fourier transforms via multi-layer sparse approximations

Abstract

The Fast Fourier Transform (FFT) is an algorithm of paramount importance in signal processing as it allows to apply the Fourier transform in O(n log n) instead of O(n 2) arithmetic operations. Graph Signal Processing (GSP) is a recent research domain that generalizes classical signal processing tools, such as the Fourier transform, to situations where the signal domain is given by any arbitrary graph instead of a regular grid. Today, there is no method to rapidly apply graph Fourier transforms. We propose in this paper a method to obtain approximate graph Fourier transforms that can be applied rapidly and stored efficiently. It is based on a greedy approximate diagonalization of the graph Laplacian matrix, carried out using a modified version of the famous Jacobi eigenvalues algorithm. The method is described and analyzed in detail, and then applied to both synthetic and real graphs, showing its potential.

References in corpus (10)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• GSPBOX: A toolbox for signal processing on graphs
• Powers of Tensors and Fast Matrix Multiplication
• Trainlets: Dictionary Learning in High Dimensions
• Treelets--An adaptive multi-scale basis for sparse unordered data
• Compressive Spectral Clustering
• Flexible Multi-layer Sparse Approximations of Matrices and Applications
• Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors

Cited by in corpus (17)

• DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications
• Sampling Signals on Graphs: From Theory to Applications
• Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling
• A Directed Graph Fourier Transform with Spread Frequency Components
• Generalized Sampling on Graphs With Subspace and Smoothness Priors
• Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
• Fast Graph Fourier Transforms Based on Graph Symmetry and Bipartition
• Bayesian Estimation of Graph Signals
• Graph Fourier Transform Based on ${\ell }_1$ Norm Variation Minimization
• Joint Time-Vertex Fractional Fourier Transform
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
• Approximating Orthogonal Matrices with Effective Givens Factorization
• Prediction and Sampling with Local Graph Transforms for Quasi-Lossless Light Field Compression
• Predictive Generalized Graph Fourier Transform for Attribute Compression of Dynamic Point Clouds
• Signal Processing on Directed Graphs
• Constructing fast approximate eigenspaces with application to the fast graph Fourier transforms
• On Sparse Graph Fourier Transform