Blue-Noise Sampling of Graph and Multigraph Signals: Dithering on Non-Euclidean Domains

With the surge in the volumes and dimensions of data defined in non-Euclidean spaces, graph signal processing (GSP) techniques are emerging as important tools in our understanding of these domains [1]. A fundamental problem for GSP is to determine which nodes play the most important role; so, graph signal sampling and recovery thus become essential [2]. In general, most of the current sampling methods are based on graph spectral decompositions where the graph Fourier transform (GFT) plays a central role [2]. Although adequate in many cases, they are not applicable when the graphs are large and where spectral decompositions are computationally difficult [3]. After years of beautiful and useful theoretical insights developed in this problem, the interest has now centered on finding more efficient methods for the computation of good sampling sets. Looking to the spatial domain for inspiration, substantial research has been performed that looks at the use of spatial point processes to define stochastic sampling grids with a particular interest at point processes that generate "blue noise."