Title: Robust Estimation of Smooth Graph Signals from Randomized Space-time Samples

Abstract: Heat diffusion processes have found wide applications in modeling dynamical system over graphs. In this talk, I will talk about the recovery of a k-bandlimited graph signal that is an initial signal of a heat diffusion process from its space-time samples. In this work, we have proposed 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. 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 on support our theoretical findings and demonstrate the efficiency.