Low-complexity Graph Sampling With Noise and Signal Reconstruction via Neumann Series
- 9 September 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 67 (21) , 5511-5526
Abstract
Graph sampling addresses the problem of selecting a node subset in a graph to collect samples, so that a $K$ -bandlimited signal can be reconstructed in high fidelity. Assuming an independent and identically distributed (i.i.d.) noise model, minimizing the expected mean square error (MMSE) leads to the known A-optimality criterion for graph sampling, which is expensive to compute and difficult to optimize. In this paper, we propose an augmented objective based on Neumann series that well approximates the original criterion and is amenable to greedy optimization. Specifically, we show that a shifted A-optimal criterion can be equivalently written as a function of an ideal low-pass (LP) graph filter, which in turn can be approximated efficiently via fast graph Fourier transform (FGFT). Minimizing the new objective, we select nodes greedily without large matrix inversions using a matrix inverse lemma. Further, for the dynamic network case where node availability varies across time, we propose an extended sampling strategy that replaces offline samples one-by-one in the selected set. For signal reconstruction, we propose an accompanied biased signal recovery strategy that reuses the approximated filter from sampling. Experiments show that our reconstruction is more robust to large noise than the least square (LS) solution, and our sampling strategy far outperforms several existing schemes.
Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61771356)
- CSC's scholarship
- Natural Sciences and Engineering Research Council of Canada (RGPIN-2019-06271, RGPAS-2019-00110)
This publication has 47 references indexed in Scilit:
- Discrete Signal Processing on Graphs: Sampling TheoryIEEE Transactions on Signal Processing, 2015
- Distributed Sparsity-Aware Sensor SelectionIEEE Transactions on Signal Processing, 2015
- Sampling theory for graph signals2015
- Big Data Analysis with Signal Processing on Graphs: Representation and processing of massive data sets with irregular structureIEEE Signal Processing Magazine, 2014
- Towards a sampling theorem for signals on arbitrary graphs2014
- Wavelets on graphs via spectral graph theoryApplied and Computational Harmonic Analysis, 2011
- Predicting Positive p53 Cancer Rescue Regions Using Most Informative Positive (MIP) Active LearningPLOS Computational Biology, 2009
- Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient MethodSIAM Journal on Scientific Computing, 2001
- Eigenvalue computation in the 20th century2001
- Updating the Inverse of a MatrixSIAM Review, 1989