Sparse Quantized Spectral Clustering
arXiv:2010.01376
Abstract
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.
References in corpus (10)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Central limit theorem for linear eigenvalue statistics of random matrices with independent entries
- Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data
- Stochastic Subsampling for Factorizing Huge Matrices
- Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures
- Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networks
- Lecture Notes on Spectral Graph Methods
- Inner-product Kernels are Asymptotically Equivalent to Binary Discrete Kernels