  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.
