Random sampling of bandlimited signals on graphs

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, \ie, 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(\nbClass \log(\nbClass))$ measurements are sufficient to ensure an accurate and stable recovery of all $\nbClass$-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.


Year:
2015
Keywords:
Laboratories:




 Record created 2015-11-17, last modified 2018-11-14

Preprint:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)