# A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series

arXiv: https://arxiv.org/abs/1803.03353 · HTML: https://mlsanity.com/paper/1803.03353/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2018.

## Built on by (most cited first, 3 of 3)

- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)

## Abstract (arXiv)

Graph signal processing (GSP) studies signals that live on irregular data kernels described by graphs. One fundamental problem in GSP is sampling---from which subset of graph nodes to collect samples in order to reconstruct a bandlimited graph signal in high fidelity. In this paper, we seek a sampling strategy that minimizes the mean square error (MSE) of the reconstructed bandlimited graph signals assuming an independent and identically distributed (iid) noise model---leading naturally to the A-optimal design criterion. To avoid matrix inversion, we first prove that the inverse of the information matrix in the A-optimal criterion is equivalent to a Neumann matrix series. We then transform the truncated Neumann series based sampling problem into an equivalent expression that replaces eigenvectors of the Laplacian operator with a sub-matrix of an ideal low-pass graph filter. Finally, we approximate the ideal filter using a Chebyshev matrix polynomial. We design a greedy algorithm to iteratively minimize the simplified objective. For signal reconstruction, we propose an accompanied signal reconstruction strategy that reuses the approximated filter sub-matrix and is provably more robust than conventional least square recovery. Simulation results show that our sampling strategy outperforms two previous strategies in MSE performance at comparable complexity.