# Random sampling of bandlimited signals on graphs

arXiv: https://arxiv.org/abs/1511.05118 · HTML: https://mlsanity.com/paper/1511.05118/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2015.

## Built on by (most cited first, 15 of 15)

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Spectrally Pruned Gaussian Fields with Neural Compensation](https://mlsanity.com/paper/2405.00676/) (2024)
- [A Computational Framework for Modeling Complex Sensor Network Data Using Graph Signal Processing and Graph Neural Networks in Structural Health Monitoring](https://mlsanity.com/paper/2105.05316/) (2021)
- [Sampling and Uniqueness Sets in Graphon Signal Processing](https://mlsanity.com/paper/2401.06279/) (2024)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Time-Vertex Machine Learning for Optimal Sensor Placement in Temporal Graph Signals: Applications in Structural Health Monitoring](https://mlsanity.com/paper/2512.19309/) (2025)
- [Learning Graph from Smooth Signals under Partial Observation: A Robustness Analysis](https://mlsanity.com/paper/2509.14887/) (2025)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)
- [Sampling Method for Generalized Graph Signals with Pre-selected Vertices via DC Optimization](https://mlsanity.com/paper/2509.14836/) (2025)
- [Randomized Space-Time Sampling for Affine Graph Dynamical Systems](https://mlsanity.com/paper/2509.16818/) (2025)
- [Random Wavelet Features for Graph Kernel Machines](https://mlsanity.com/paper/2602.15711/) (2026)
- [Multilevel Graph Wavelet Compressed Sensing with Scale-Aware Neural Recovery](https://mlsanity.com/paper/2607.20857/) (2026)
- [Scalable Graph Coreset Selection via Greedy Sampling](https://mlsanity.com/paper/2607.27602/) (2026)

## Abstract (arXiv)

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.