Nicolas Tremblay's randomsampling

Random sampling of bandlimited signals on graphs

How can one sample a k-bandlimited signal on a graph --i.e. a "smooth" signal whose k first graph Fourier coefficients are non-null-- while still being able to recover it perfectly?

The goals here are both to reduce as much as possible the number of samples, while garanteeing robust reconstruction with respect to noise. Recent litterature on this subject (see the introduction of our paper for references) suggests that there always exists a sampling set of size k that perfectly embeds k-bandlimited signals. The difficulty is to find this optimal set: it is a difficult combinatorial problem that cannot scale to large graphs.

In our approach, we propose a very different approach to sampling on graphs. Instead of trying to find an optimal sampling set for k-bandlimited signals, we relax this optimality constraint in order to tackle graphs of very large size. We allow ourselves to sample slightly more than k nodes and, inspired by compressive sampling, we propose two random sampling schemes that ensure recovery of graph signals with high probability:
1) The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence.
2) On the contrary, the second strategy is adaptive and 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.
We finally propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is stable to noise.

Associated paper: Gilles Puy, Nicolas Tremblay, RĂ©mi Gribonval, Pierre Vandergheynst. Random sampling of bandlimited signals on graphs. In ARXIV, 1511.05118, 2015. [PDF]