Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Fast Sampling of Graph Signals with Noise via Neumann Series Conversion

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.

up
0 users have voted:

Paper Details

Authors:
Gene Cheung; Yongchao Wang
Submitted On:
8 May 2019 - 12:17pm
Short Link:
Type:
Poster
Event:
Presenter's Name:
Gene Cheung
Paper Code:
ICASSP19005
Document Year:
2019
Cite

Document Files

A-optimal graph sampling

(39)

Keywords

Additional Categories

Subscribe

[1] Gene Cheung; Yongchao Wang, "Fast Sampling of Graph Signals with Noise via Neumann Series Conversion", IEEE SigPort, 2019. [Online]. Available: http://sigport.org/4121. Accessed: Oct. 15, 2019.
@article{4121-19,
url = {http://sigport.org/4121},
author = {Gene Cheung; Yongchao Wang },
publisher = {IEEE SigPort},
title = {Fast Sampling of Graph Signals with Noise via Neumann Series Conversion},
year = {2019} }
TY - EJOUR
T1 - Fast Sampling of Graph Signals with Noise via Neumann Series Conversion
AU - Gene Cheung; Yongchao Wang
PY - 2019
PB - IEEE SigPort
UR - http://sigport.org/4121
ER -
Gene Cheung; Yongchao Wang. (2019). Fast Sampling of Graph Signals with Noise via Neumann Series Conversion. IEEE SigPort. http://sigport.org/4121
Gene Cheung; Yongchao Wang, 2019. Fast Sampling of Graph Signals with Noise via Neumann Series Conversion. Available at: http://sigport.org/4121.
Gene Cheung; Yongchao Wang. (2019). "Fast Sampling of Graph Signals with Noise via Neumann Series Conversion." Web.
1. Gene Cheung; Yongchao Wang. Fast Sampling of Graph Signals with Noise via Neumann Series Conversion [Internet]. IEEE SigPort; 2019. Available from : http://sigport.org/4121