Discrete Signal Processing on Graphs: Sampling Theory
From MaRDI portal
Abstract: We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for ErdH{o}s-R'enyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification on online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.
Cited in
(34)- Polynomial control on stability, inversion and powers of matrices on simple graphs
- A low discrepancy sequence on graphs
- The dual graph shift operator: identifying the support of the frequency domain
- Subset selection for matrices with fixed blocks
- Localized Fourier analysis for graph signal processing
- Graph signal interpolation with positive definite graph basis functions
- Extrapolation and sampling for processes on spatial graphs
- Local smoothness of graph signals
- Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
- Graph Fourier transform based on \(\ell_1\) norm variation minimization
- Overview of the topical collection: harmonic analysis on combinatorial graphs
- Approximating spectral clustering via sampling: a review
- Half sampling on bipartite graphs
- Discrete Signal Processing on Graphs
- Extending Classical Multirate Signal Processing Theory to Graphs—Part I: Fundamentals
- Transferability of spectral graph convolutional neural networks
- Signal Processing on Simplicial Complexes
- Data Analytics on Graphs Part II: Signals on Graphs
- Generalizing Graph Signal Processing: High Dimensional Spaces, Models and Structures
- Graph Fourier transform based on singular value decomposition of the directed Laplacian
- A class of doubly stochastic shift operators for random graph signals and their boundedness
- Spectral Laplace transform of signals on arbitrary domains
- Graphical designs and gale duality
- Robust estimation of smooth graph signals from randomized space-time samples
- Random space-time sampling and reconstruction of sparse bandlimited graph diffusion field
- Sparse graphical designs via linear programming
- Sparse graph signals -- uncertainty principles and recovery
- Continuous spectral transform and modulation for signal processing on arbitrary data
- Subset selection for matrices in spectral norm
- Translation operator and frames on directed graphs
- Calculating the spectral factorization and outer functions by sampling-based approximations -- fundamental limitations
- Approximation theorems on graphs
- Graph signal sampling and interpolation based on clusters and averages
- Spatio-spectral limiting on Boolean cubes
This page was built for publication: Discrete Signal Processing on Graphs: Sampling Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580962)
