# Practical graph signal sampling with log-linear size scaling

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2021.

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

- [Sampling and Uniqueness Sets in Graphon Signal Processing](https://mlsanity.com/paper/2401.06279/) (2024)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (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)

## Abstract (arXiv)

Graph signal sampling is the problem of selecting a subset of representative graph vertices whose values can be used to interpolate missing values on the remaining graph vertices. Optimizing the choice of sampling set using concepts from experiment design can help minimize the effect of noise in the input signal. While many existing sampling set selection methods are computationally intensive because they require an eigendecomposition, existing eigendecompostion-free methods are still much slower than random sampling algorithms for large graphs. In this paper, through optimizing sampling sets towards the D-optimal objective from experiment design, we propose a sampling algorithm that has complexity comparable to random sampling algorithms, while reaching accuracy similar to existing eigendecomposition-free methods for a broad range of graph types.