Random sampling of bandlimited signals on graphs - Inserm - Institut national de la santé et de la recherche médicale Accéder directement au contenu
Article Dans Une Revue Applied and Computational Harmonic Analysis Année : 2018

Random sampling of bandlimited signals on graphs

Résumé

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. [Code available at http://grsamplingbox.gforge.inria.fr/]
Fichier principal
Vignette du fichier
main.pdf (7.79 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01229578 , version 1 (16-11-2015)
hal-01229578 , version 2 (20-05-2016)
hal-01229578 , version 3 (27-07-2016)

Identifiants

Citer

Gilles Puy, Nicolas Tremblay, Rémi Gribonval, Pierre Vandergheynst. Random sampling of bandlimited signals on graphs. Applied and Computational Harmonic Analysis, 2018, 44 (2), pp.446-475. ⟨10.1016/j.acha.2016.05.005⟩. ⟨hal-01229578v3⟩
486 Consultations
889 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More