Graph sampling with determinantal processes
This addresses the challenge of signal recovery on graphs for applications requiring minimal measurements, particularly in graphs with strong community structures, though it is incremental in adapting DPP methods to graph contexts.
The paper tackles the problem of sampling k-bandlimited signals on graphs by introducing a new random sampling strategy based on determinantal point processes (DPP), achieving perfect recovery for small graphs and efficient, promising results for large graphs with up to 10^6 nodes.
We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, in cases where the graph's spectrum is not accessible, we investigate, both theoretically and empirically, a sub-optimal but much faster DPP based on loop-erased random walks on the graph. Preliminary experiments show promising results especially in cases where the number of measurements should stay as small as possible and for graphs that have a strong community structure. Our sampling scheme is efficient and can be applied to graphs with up to $10^6$ nodes.