Fast Sampling of Graph Signals with Noise via Neumann Series Conversion
Lists
Only you see this
Abstract
Graph sampling with independent noise towards minimum mean square error (MMSE) leads to the known A-optimality criterion, which is computation-intensive to evaluate and NP-hard to optimize. In this paper, we propose a new low-complexity sampling strategy based on Neumann series that circumvents large matrix inversion and eigen-decomposition. We first prove that a DC-shifted A-optimality criterion is equivalent to an objective computed using the inverse of a sub-matrix of an ideal graph low-pass (LP) filter. The LP filter matrix can be approximated efficiently via fast Graph Fourier Transform (FGFT). Using the shifted A-optimality objective as a proxy, we then propose a fast algorithm to greedily select samples one-by-one based on a matrix inversion lemma with simple matrix updates. We show that the obtained solution has a performance upper bound via super-modularity analysis. Simulation results show that our proposed sampling strategy has lower complexity and outperforms several existing deterministic sampling schemes.
BibTeX
@inproceedings{wang2019fast,
author = {Fen Wang and Gene Cheung and Yongchao Wang},
title = {{Fast Sampling of Graph Signals with Noise via Neumann Series Conversion}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2019},
doi = {10.1109/icassp.2019.8682564},
}Loading related content...