  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 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, we
propose a sampling algorithm that can achieve speeds similar to random
sampling, while reaching accuracy similar to existing eigendecomposition-free
methods for a broad range of graph types.
