Online Program Home
My Program

Abstract Details

Activity Number: 566 - Nonparametrics on Graphs
Type: Invited
Date/Time: Wednesday, August 1, 2018 : 2:00 PM to 3:50 PM
Sponsor: IMS
Abstract #333151
Title: Fundamental Limits of Sampling Smooth Signals on Graphs
Author(s): Rohan A. Varma* and Aarti Singh
Companies: Carnegie Mellon University and Carnegie Mellon University

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.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2018 program