Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
arXiv:1512.05405
Abstract
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 these three sampling strategies and show that active sampling cannot fundamentally outperform experimentally designed sampling. We 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 for each sampling strategy. To study convergence rates, we introduce two types of graphs and find that (1) the proposed recovery strategy achieves the optimal rates; and (2) the experimentally designed sampling fundamentally outperforms uniform sampling for Type-2 class of graphs. To validate our proposed recovery strategy, we test it on five specific graphs: a ring graph with nearest neighbors, an Erdős-Rényi 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 also presents a comprehensive explanation for when and why sampling for semi-supervised learning with graphs works.
arXiv commentIEEE Trans. Signal and Inform. Process. over Networks, sp. iss. Inference and Learning over Networks
References in corpus (20)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Random Geometric Graphs
- Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Signals on Graphs: Uncertainty Principle and Sampling
- Signal Recovery on Graphs: Variation Minimization
- Sampling of graph signals with successive local aggregations
- Spectra and eigenvectors of scale-free networks
- Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
- Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
- A Spectral Graph Uncertainty Principle
- Local-set-based Graph Signal Reconstruction
- Learning parametric dictionaries for graph signals
- Reconstruction of Graph Signals through Percolation from Seeding Nodes
- A Distributed Tracking Algorithm for Reconstruction of Graph Signals
- Signal Representations on Graphs: Tools and Applications
- Localization on low-order eigenvectors of data matrices
- Local Measurement and Reconstruction for Noisy Graph Signals