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

By Aamir Anis, Akshay Gadde, Antonio Ortega. IEEE Transactions on Signal Processing, 2015

351 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/70b0f299d5838aecf6386fb53429407487cae1a8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Graph Learning From Data Under Laplacian and Structural Constraints (2016, methodology): “Moreover, in graph signal processing [4], basic signal processing operations such as filtering [10] [20], sampling [21], transformation [9] [22] are extended to signals defined on graphs associated with Laplacian matrices.”
Global and Local Uncertainty Principles for Signals on Graphs (2016, background): “However, for the curious reader, they exists many contributions addressing the slightly different problem of active sampling [75, 76].”
Graph Signal Processing: Overview, Challenges, and Applications (2017, methodology): “technique, it may not always lead to performance comparable to those of more complex greedy optimization methods such as [121], [122].”
Compressive Spectral Clustering (2016, background): “There has been recently a surge of interest around adapting classical sampling theorems to such bandlimited graph signals (Anis et al., 2015; Chen et al., 2015; Marques et al., 2015; Tsitsvero et al., 2015).”
Convolutional Neural Network Architectures for Signals Supported on Graphs (2018, methodology): “First, we choose nodes based on their degree; second, we select them following the leverage scores proposed by the experimentally designed sampling (EDS) in [32]; and third, we determine the appropriate nodes by using the spectral-proxies approach (SP) in [29].”