Sampling and Reconstruction of Sparse Signals on Circulant Graphs - An Introduction to Graph-FRI
arXiv:1606.08085 · doi:10.1016/j.acha.2017.10.003
Abstract
With the objective of employing graphs toward a more generalized theory of signal processing, we present a novel sampling framework for (wavelet-)sparse signals defined on circulant graphs which extends basic properties of Finite Rate of Innovation (FRI) theory to the graph domain, and can be applied to arbitrary graphs via suitable approximation schemes. At its core, the introduced Graph-FRI-framework states that any K-sparse signal on the vertices of a circulant graph can be perfectly reconstructed from its dimensionality-reduced representation in the graph spectral domain, the Graph Fourier Transform (GFT), of minimum size 2K. By leveraging the recently developed theory of e-splines and e-spline wavelets on graphs, one can decompose this graph spectral transformation into the multiresolution low-pass filtering operation with a graph e-spline filter, and subsequent transformation to the spectral graph domain; this allows to infer a distinct sampling pattern, and, ultimately, the structure of an associated coarsened graph, which preserves essential properties of the original, including circularity and, where applicable, the graph generating set.
arXiv commentTo appear in Appl. Comput. Harmon. Anal. (2017)
References in corpus (12)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs: Sampling Theory
- Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
- Signal Recovery on Graphs: Variation Minimization
- Sampling of graph signals with successive local aggregations
- Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
- Local-set-based Graph Signal Reconstruction
- Compressed Sensing with Coherent and Redundant Dictionaries
- Splines and Wavelets on Circulant Graphs
- Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
- A Multiscale Pyramid Transform for Graph Signals
- Estimation of Laplacian spectra of direct and strong product graphs
Cited by in corpus (8)
- Splines and Wavelets on Circulant Graphs
- A Graph Signal Processing View on Functional Brain Imaging
- Detecting Localized Categorical Attributes on Graphs
- Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
- Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering
- Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
- Analysis vs Synthesis with Structure - An Investigation of Union of Subspace Models on Graphs
- Weighted sampling and weighted interpolation on combinatorial graphs