Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies

DOI10.1109/TSP.2016.2546233MaRDI QIDQ4622066zbMATH OpenFDO

Authors Aamir Anis, Akshay Gadde, Antonio Ortega

Publication date 8 February 2019

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

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Abstract: We study the problem of selecting the best sampling set for bandlimited reconstruction of signals on graphs. A frequency domain representation for graph signals can be defined using the eigenvectors and eigenvalues of variation operators that take into account the underlying graph connectivity. Smoothly varying signals defined on the nodes are of particular interest in various applications, and tend to be approximately bandlimited in the frequency basis. Sampling theory for graph signals deals with the problem of choosing the best subset of nodes for reconstructing a bandlimited signal from its samples. Most approaches to this problem require a computation of the frequency basis (i.e., the eigenvectors of the variation operator), followed by a search procedure using the basis elements. This can be impractical, in terms of storage and time complexity, for real datasets involving very large graphs. We circumvent this issue in our formulation by introducing quantities called graph spectral proxies, defined using the powers of the variation operator, in order to approximate the spectral content of graph signals. This allows us to formulate a direct sampling set selection approach that does not require the computation and storage of the basis elements. We show that our approach also provides stable reconstruction when the samples are noisy or when the original signal is only approximately bandlimited. Furthermore, the proposed approach is valid for any choice of the variation operator, thereby covering a wide range of graphs and applications. We demonstrate its effectiveness through various numerical experiments.

Cited in

(15)

• Random sampling of bandlimited signals on graphs
• A low discrepancy sequence on graphs
• Codes, cubes, and graphical designs
• Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
• Extrapolation and sampling for processes on spatial graphs
• scientific article; zbMATH DE number 7008335 (Why is no real title available?)
• Invertibility of graph translation and support of Laplacian Fiedler vectors
• Data Analytics on Graphs Part II: Signals on Graphs
• Generalizing Graph Signal Processing: High Dimensional Spaces, Models and Structures
• Graphical designs and gale duality
• Bayesian reconstruction of Cartesian product graph signals with general patterns of missing data
• 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
• Approximation theorems on graphs

This page was built for publication: Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4622066)