Discrete Signal Processing on Graphs: Sampling Theory

DOI10.1109/TSP.2015.2469645MaRDI QIDQ4580962zbMATH OpenOpenAlexFDO

Authors Siheng Chen, Rohan Varma, Aliaksei Sandryhaila, Jelena Kovačević

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.05432

Mathematics Subject Classification ID

Applications of graph theory (05C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

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

(28)

• Overview of the topical collection: harmonic analysis on combinatorial graphs
• Extrapolation and sampling for processes on spatial graphs
• Signal Processing on Simplicial Complexes
• Approximation theorems on graphs
• Graph signal sampling and interpolation based on clusters and averages
• Spatio-spectral limiting on Boolean cubes
• The dual graph shift operator: identifying the support of the frequency domain
• Local smoothness of graph signals
• Calculating the spectral factorization and outer functions by sampling-based approximations -- fundamental limitations
• Localized Fourier analysis for graph signal processing
• A low discrepancy sequence on graphs
• Graph Fourier transform based on \(\ell_1\) norm variation minimization
• Discrete Signal Processing on Graphs
• Graphical designs and gale duality
• Polynomial control on stability, inversion and powers of matrices on simple graphs
• Subset selection for matrices with fixed blocks
• Spectral Laplace transform of signals on arbitrary domains
• Approximating spectral clustering via sampling: a review
• Robust estimation of smooth graph signals from randomized space-time samples
• scientific article; zbMATH DE number 7626787 (Why is no real title available?)
• A class of doubly stochastic shift operators for random graph signals and their boundedness
• Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
• Half sampling on bipartite graphs
• Extending Classical Multirate Signal Processing Theory to Graphs—Part I: Fundamentals
• Graph signal interpolation with positive definite graph basis functions
• Generalizing Graph Signal Processing: High Dimensional Spaces, Models and Structures
• Graph Fourier transform based on singular value decomposition of the directed Laplacian
• Data Analytics on Graphs Part II: Signals on Graphs

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)