# Blue-Noise Sampling on Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

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

- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs](https://mlsanity.com/paper/2212.08171/) (2022)
- [Sampling and Uniqueness Sets in Graphon Signal Processing](https://mlsanity.com/paper/2401.06279/) (2024)
- [Graph CNN for Moving Object Detection in Complex Environments from Unseen Videos](https://mlsanity.com/paper/2207.06440/) (2022)
- [Time-varying Signals Recovery via Graph Neural Networks](https://mlsanity.com/paper/2302.11313/) (2023)

## Abstract (arXiv)

In the area of graph signal processing, a graph is a set of nodes arbitrarily connected by weighted links; a graph signal is a set of scalar values associated with each node; and sampling is the problem of selecting an optimal subset of nodes from which a graph signal can be reconstructed. This paper proposes the use of spatial dithering on the vertex domain of the graph, as a way to conveniently find statistically good sampling sets. This is done establishing that there is a family of good sampling sets characterized on the vertex domain by a maximization of the distance between sampling nodes; in the Fourier domain, these are characterized by spectrums that are dominated by high frequencies referred to as blue-noise. The theoretical connection between blue-noise sampling on graphs and previous results in graph signal processing is also established, explaining the advantages of the proposed approach. Restricting our analysis to undirected and connected graphs, numerical tests are performed in order to compare the effectiveness of blue-noise sampling against other approaches.