Échantillonnage de signaux sur graphes via des processus déterminantaux
This addresses the computational bottleneck in large-scale graph signal processing by enabling efficient sampling and reconstruction for applications like sensor networks or data analysis on graphs.
The paper tackles the problem of sampling k-bandlimited graph signals without needing to partially diagonalize the graph Laplacian, proposing a strategy based on determinantal point processes that achieves perfect reconstruction with only O(k) samples and introduces a faster sampling algorithm.
We consider the problem of sampling k-bandlimited graph signals, ie, linear combinations of the first k graph Fourier modes. We know that a set of k nodes embedding all k-bandlimited signals always exists, thereby enabling their perfect reconstruction after sampling. Unfortunately, to exhibit such a set, one needs to partially diagonalize the graph Laplacian, which becomes prohibitive at large scale. We propose a novel strategy based on determinantal point processes that side-steps partial diagonalisation and enables reconstruction with only O(k) samples. While doing so, we exhibit a new general algorithm to sample determinantal process, faster than the state-of-the-art algorithm by an order k.