Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Random sampling of bandlimited signals on graphs

Gilles Puy 1 Nicolas Tremblay 1, 2 Rémi Gribonval 1 Pierre Vandergheynst 1, 2
1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
Abstract : We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than O(k log(k)) measurements are sufficient to ensure an accurate and stable recovery of all k-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01229578
Contributor : Gilles Puy <>
Submitted on : Monday, November 16, 2015 - 10:05:53 PM
Last modification on : Thursday, November 15, 2018 - 11:58:46 AM
Document(s) archivé(s) le : Friday, April 28, 2017 - 9:54:18 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01229578, version 1

Citation

Gilles Puy, Nicolas Tremblay, Rémi Gribonval, Pierre Vandergheynst. Random sampling of bandlimited signals on graphs. 2015. ⟨hal-01229578v1⟩

Share

Metrics

Record views

152

Files downloads

1058