|
Abstract:
|
In this talk, we discuss the sampling and recovery of smooth signals on weighted graphs under different sampling paradigms. Specifically, we consider random sampling, passive experimentally-designed sampling and active sampling strategies, and construct minimax lower-bounds for the same. We use the graph signal processing framework under which smooth signals are approximately bandlimited under the graph Fourier transform. We derive a signal recovery strategy and study its convergence rates on different classes of graphs, for both uniform and passive experimentally-designed sampling, demonstrating that the strategy is nearly minimax optimal. Particularly, we look at how structural properties of the graph drive the performance of these sampling and recovery algorithms, both theoretically and empirically with real-world graphs. We conclude that the structure of the graph can be leveraged using experimental design to get better performance than uniform sampling, however, active sampling cannot fundamentally outperform passive experimentally designed sampling. We also emphasize connections to semi-supervised learning on graphs.
|
