  Graph signal sampling is the problem of selecting a subset of representative
graph vertices whose values can be used to interpolate missing values on the
remaining graph vertices. Optimizing the choice of sampling set using concepts
from experiment design can help minimize the effect of noise in the input
signal. While many existing sampling set selection methods are computationally
intensive because they require an eigendecomposition, existing
eigendecompostion-free methods are still much slower than random sampling
algorithms for large graphs. In this paper, through optimizing sampling sets
towards the D-optimal objective from experiment design, we propose a sampling
algorithm that has complexity comparable to random sampling algorithms, while
reaching accuracy similar to existing eigendecomposition-free methods for a
broad range of graph types.
