Discrete Signal Processing on Graphs: Sampling Theory

DOI10.1109/TSP.2015.2469645zbMATH Open1395.94094arXiv1503.05432OpenAlexW2161763921MaRDI QIDQ4580962FDOQ4580962

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

Publication date: 22 August 2018

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

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.

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)

Cited In (28)

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

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)