Title:Robust recovery of bandlimited graph signals via randomized dynamical sampling

Abstract:Heat diffusion processes have found wide applications in modelling dynamical systems over graphs. In this paper, we consider the recovery of a $k$-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 $\mathcal{O}(k \log(k))$ space-time samples are sufficient to ensure accurate and stable recovery of all $k$-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 $k$-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.