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.