compendium

S. Chen, R. Varma, A. Singh, and J. Kovačević. Signal recovery on graphs: Fundamental limits of sampling strategies. IEEE Trans, Signal and Inform. Process. over Networks, 2016. Submitted.

[ pdf | @ arXiv | bibtex]

This paper builds theoretical foundations for the recovery of a newly proposed class of smooth graph signals, approximately bandlimited graph signals, under three sampling strategies: uniform sampling, experimentally designed sampling and active sampling. We then state minimax lower bounds on the maximum risk for the approximately bandlimited class under three sampling strategies and show that active sampling cannot fundamentally outperform experimentally designed sampling. We then propose a recovery strategy to compare uniform sampling with experimentally designed sampling. As the proposed recovery strategy lends itself well to statistical analysis, we derive the exact mean square error of each sampling strategy. To study convergence rates, we introduce two types of graphs and find that (1) the proposed recovery strategies achieve the optimal rates; and (2) the experimentally designed sampling fundamentally outperforms uniform sampling for type-2 class of graphs. To validate our proposed recovery strategies, we test them on five specific graphs: a ring graph with k nearest neighbors, an Erdos-Renyi graph graph, a random geometric graph, a small-world graph and a power-law graph and find that experimental results match the proposed theory well. This work shows a comprehensive explanation for when and why sampling for semi-supervised learning with graphs works.

This work is licensed under a Creative Commons GNU General Public License. To view a copy of this license, visit http://creativecommons.org/licenses/GPL/2.0. If you use this code or any part thereof in your research or publication, please also include a reference to this paper. Thank you!

N/A

N/A

N/A

contact

For more information or to report bugs contact jelenak at cmu dot edu.