paper

Robust recovery of bandlimited graph signals via randomized dynamical sampling

arXiv:2109.14079

Abstract

Heat diffusion processes have found wide applications in modelling dynamical systems over graphs. In this paper, we consider the recovery of a -bandlimited graph signal that is an initial signal of a heat diffusion process from its space-time samples. We propose three random space-time sampling regimes, termed dynamical sampling techniques, that consist in selecting a small subset of space-time nodes at random according to some probability distribution. We show that the number of space-time samples required to ensure stable recovery for each regime depends on a parameter called the spectral graph weighted coherence, that depends on the interplay between the dynamics over the graphs and sampling probability distributions. In optimal scenarios, no more than space-time samples are sufficient to ensure accurate and stable recovery of all -bandlimited signals. In any case, dynamical sampling typically requires much fewer spatial samples than the static case by leveraging the temporal information. Then, we propose a computationally efficient method to reconstruct -bandlimited signals from their space-time samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we test dynamical sampling techniques on a wide variety of graphs. The numerical results support our theoretical findings and demonstrate the efficiency.

arXiv commentcorrected mistakes in plotting. arXiv admin note: text overlap with arXiv:1511.05118 by other authors

References in corpus (10)