## Random sampling of bandlimited signals on graphs.(English)Zbl 1391.94367

Summary: 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.

### MSC:

 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 94A20 Sampling theory in information and communication theory 05C90 Applications of graph theory 94C15 Applications of graph theory to circuits and networks

### Keywords:

graph signal processing; sampling; compressed sensing

GSPBOX; PyGSP
Full Text: