Sparse Quantized Spectral Clustering
  Given a large data matrix, sparsifying, quantizing, and/or performing other
entry-wise nonlinear operations can have numerous benefits, ranging from
speeding up iterative algorithms for core numerical linear algebra problems to
providing nonlinear filters to design state-of-the-art neural network models.
Here, we exploit tools from random matrix theory to make precise statements
about how the eigenspectrum of a matrix changes under such nonlinear
transformations. In particular, we show that very little change occurs in the
informative eigenstructure even under drastic sparsification/quantization, and
consequently that very little downstream performance loss occurs with very
aggressively sparsified or quantized spectral clustering. We illustrate how
these results depend on the nonlinearity, we characterize a phase transition
beyond which spectral clustering becomes possible, and we show when such
nonlinear transformations can introduce spurious non-informative eigenvectors.
