Sampling of Graph Signals with Successive Local Aggregations

A. Marques, S. Segarra, G. Leus, A. Ribeiro

Research output: Contribution to journalArticleScientificpeer-review

150 Citations (Scopus)


A new scheme to sample signals defined on the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Instead of using the value of the signal observed at a subset of nodes to recover the signal in the entire graph, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, critical when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise, and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. Numerical experiments illustrating the results in both synthetic and real-world graphs close the paper.
Original languageEnglish
Pages (from-to)1832-1843
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number7
Publication statusPublished - 10 Dec 2015


  • Error covariance
  • graph signal processing
  • graph signals
  • interpolation
  • sampling
  • support selection


Dive into the research topics of 'Sampling of Graph Signals with Successive Local Aggregations'. Together they form a unique fingerprint.

Cite this