  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.
