This work concerns sampling of smooth signals on arbitrary graphs. We first study a structured sampling strategy for such smooth graph signals that consists of a random selection of few pre-defined groups of nodes. The number of groups to sample to stably embed the set of $k$-bandlimited signals is driven by a quantity called the \emph{group} graph cumulative coherence. For some optimised sampling distributions, we show that sampling $O(k\log(k))$ groups is always sufficient to stably embed the set of $k$-bandlimited signals but that this number can be smaller -- down to $O(\log(k))$ -- depending on the structure of the groups of nodes. Fast methods to approximate these sampling distributions are detailed. Second, we consider $k$-bandlimited signals that are nearly piecewise constant over pre-defined groups of nodes. We show that it is possible to speed up the reconstruction of such signals by reducing drastically the dimension of the vectors to reconstruct. When combined with the proposed structured sampling procedure, we prove that the method provides stable and accurate reconstruction of the original signal. Finally, we present numerical experiments that illustrate our theoretical results and, as an example, show how to combine these methods for interactive object segmentation in an image using superpixels.
Structured sampling and fast reconstruction of smooth graph signals
Structured sampling and fast reconstruction of smooth graph signals
Structured sampling and fast reconstruction of smooth graph signals
Related Content
To work at scale, a complete image indexing system comprises two components: An inverted file index to restrict the actual search to only a subset that should contain most of the items relevant to the query; An approximate distance computation mechanism to rapidly scan these lists. While supervised deep learning has recently enabled improvements to the latter, t…
This article presents an empirical study that investigated and compared two “big data” text analysis methods: dictionary-based analysis, perhaps the most popular automated analysis approach in social science research, and unsupervised topic modeling (i.e., Latent Dirichlet Allocation [LDA] analysis), one of the most widely used algorithms in the field of compute…
The ability of multimedia data to attract and keep people’s interest for longer periods of time is gaining more and more importance in the fields of information retrieval and recommendation, especially in the context of the ever growing market value of social media and advertising. In this chapter we introduce a benchmarking framework (dataset and evaluation too…
Webinar /Jun 2024
Blog Post /Jun 2025
Blog Post /Jun 2025