Sparse Quantized Spectral Clustering
This work addresses the problem of speeding up spectral clustering for large datasets by enabling aggressive sparsification and quantization with little performance loss, though it is incremental in applying random matrix theory to this context.
The paper analyzed how sparsification and quantization affect the eigenspectrum of matrices, showing minimal changes in informative eigenstructure and downstream performance loss in spectral clustering, with results depending on nonlinearity and including phase transition characterizations.
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.