Discrete Signal Processing on Graphs: Sampling Theory

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

Research output: Contribution to journalArticle

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 Erdo{combining double acute accent}s-Rényi 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 of online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.

Original languageEnglish (US)
Article number7208894
Pages (from-to)6510-6523
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume63
Issue number24
DOIs
StatePublished - Dec 15 2015

Keywords

  • Bandwidth
  • Electronic mail
  • Fourier transforms
  • Interpolation
  • Laplace equations
  • Robustness
  • Signal processing

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Discrete Signal Processing on Graphs: Sampling Theory'. Together they form a unique fingerprint.

  • Cite this