CoChat
Sign Up
PreprintCited by 10Advanced Clustering Algorithms ResearchSparse and Compressive Sensing TechniquesMatrix Theory and Algorithms

Sparse Quantized Spectral Clustering

Open access
Liao, Zhenyu, Couillet, Romain, Mahoney, Michael W.·2020·arXiv
DOI 10.48550/arxiv.2010.01376arXiv 2010.01376
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2010.01376

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Integer-only quantization uses low-precision integer arithmetic for all operations, allowing inference without floating-point dequantization.

    “However, in integer-only quantization, all the operations are performed using low-precision integer arithmetic [113,132,154,193,267], as illustrated in Figure 6 (Right).This permits the entire inference to be carried out with efficient integer arithmetic, without any floating point dequantization of any parameters or activations.”

    From A Survey of Quantization Methods for Efficient Neural Network Inference (2022) · cites this paper as [154]

    The Introduction (p. 2) describes quantizing a matrix for spectral clustering and reducing its storage cost. The system model (p. 3) gives bits per matrix entry, but neither passage addresses integer-only inference. Searches for low-precision integer arithmetic and floating-point dequantization found no passage supporting the claimed execution method. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

  • CMSIS-NN helps quantize and deploy neural network models onto ARM Cortex-M cores using fixed-point quantization with power-of-two scaling factors.

    “CMSIS-NN [136] is a library from ARM that helps quantizing and deploying NN models onto the ARM Cortex-M cores.Specifically, the library leverages fixed-point quantization [113,154,267] with power-oftwo scaling factors so that quantization and dequantization processes can be carried out efficiently with bit shifting operations.”

    From A Survey of Quantization Methods for Efficient Neural Network Inference (2022) · cites this paper as [154]

    The Introduction (p. 2) and Section 4.3 (pp. 9–10) discuss quantizing matrices for spectral clustering, not neural-network deployment. Searches for CMSIS-NN, ARM Cortex-M, fixed-point quantization, and power-of-two scaling found no passage addressing the attributed claim. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 49

  1. Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM) , 54(2):9-es, 2007.
  2. George E Andrews, Richard Askey, and Ranjan Roy. Special functions , volume 71. Cambridge university press, 2000.
  3. Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices , volume 20. Springer, 2010.
  4. Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability , 33(5):1643-1697, 2005.
  5. Xiuyuan Cheng. Random matrices in high-dimensional data analysis . PhD thesis, Princeton, NJ: Princeton University, 2013. URL http://arks.princeton.edu/ark:/88435/dsp01wh246s26t .
  6. Xiuyuan Cheng and Amit Singer. The spectrum of random inner-product kernel matrices. Random Matrices: Theory and Applications , 2(04):1350010, 2013.
  7. Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 or -1 . arXiv preprint arXiv:1602.02830 , 2016. · arXiv
  8. Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition , pp. 248-255. Ieee, 2009.
  9. Yen Do and Van Vu. The spectrum of random kernel matrices: universality results for rough and varying kernels. Random Matrices: Theory and Applications , 2(03):1350005, 2013.
  10. Petros Drineas and Michael W Mahoney. RandNLA: randomized numerical linear algebra. Communications of the ACM , 59(6):80-90, 2016.
  11. Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via a matrixvalued Bernstein inequality. Information Processing Letters , 111(8):385-389, 2011.
  12. Noureddine El Karoui. On information plus noise kernel random matrices. The Annals of Statistics , 38(5):3191-3216, 2010.
  13. Zhou Fan and Andrea Montanari. The spectral norm of random inner-product kernel matrices. Probability Theory and Related Fields , 173(1-2):27-85, 2019.
  14. Gene H. Golub and Charles F. Van Loan. Matrix Computations . The Johns Hopkins University Press, third edition, 1996.
  15. Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems , pp. 8571-8580, 2018.
  16. Arthur Jacot, Franck Gabriel, and Clement Hongler. The asymptotic spectrum of the Hessian of DNN throughout training. In International Conference on Learning Representations , 2019.
  17. Arun Kadavankandy and Romain Couillet. Asymptotic gaussian fluctuations of spectral clustering eigenvectors. In 2019 IEEE 8th International Workshop on Computational Advances in MultiSensor Adaptive Processing (CAMSAP) , pp. 694-698. IEEE, 2019.
  18. Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE , 86(11):2278-2324, 1998.
  19. Ping Li and Phan-Minh Nguyen. On random deep weight-tied autoencoders: Exact asymptotic analysis, phase transitions, and implications to training. In International Conference on Learning Representations , 2018.
  20. Zhenyu Liao and Romain Couillet. Inner-product kernels are asymptotically equivalent to binary discrete kernels. arXiv preprint arXiv:1909.06788 , 2019. · arXiv
  21. Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network. In Advances in Neural Information Processing Systems , pp. 345-353, 2017.
  22. Sifan Liu and Edgar Dobriban. Ridge Regression: Structure, Cross-Validation, and Sketching. In International Conference on Learning Representations , 2019.
  23. Anna Lytova and Leonid Pastur. Central limit theorem for linear eigenvalue statistics of random matrices with independent entries. The Annals of Probability , 37(5):1778-1840, 2009.
  24. Michael W Mahoney. Randomized Algorithms for Matrices and Data. Foundations and Trends® in Machine Learning , 3(2):123-224, 2011.
  25. Michael W Mahoney. Lecture notes on spectral graph methods. arXiv preprint arXiv:1608.04845 , 2016. · arXiv
  26. Vladimir A Marcenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik , 1(4):457, 1967.
  27. Charles H Martin and Michael W Mahoney. Implicit self-regularization in deep neural networks: Evidence from random matrix theory and implications for learning. arXiv preprint arXiv:1810.01075 , 2018. · arXiv
  28. Charles H Martin and Michael W Mahoney. Traditional and heavy tailed self regularization in neural network models. In International Conference on Machine Learning , pp. 4284-4293, 2019.
  29. Charles H Martin and Michael W Mahoney. Heavy-tailed universality predicts trends in test accuracies for very large pre-trained deep neural networks. In Proceedings of the 2020 SIAM International Conference on Data Mining , pp. 505-513. SIAM, 2020a.
  30. Charles H Martin and Michael W Mahoney. Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data. arXiv preprint arXiv:2002.06716 , 2020b. · arXiv
  31. Arthur Mensch, Julien Mairal, Bertrand Thirion, and Gaël Varoquaux. Stochastic subsampling for factorizing huge matrices. IEEE Transactions on Signal Processing , 66(1):113-128, 2017.
  32. Vinay Uday Prabhu. Kannada-MNIST: A new handwritten digits dataset for the Kannada language. arXiv preprint arXiv:1908.01242 , 2019. · arXiv
  33. Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems , pp. 1177-1184, 2008.
  34. Farbod Roosta-Khorasani and Michael W Mahoney. Sub-sampled Newton methods. Mathematical Programming , 174(1-2):293-326, 2019.
  35. Walter Rudin. Principles of mathematical analysis , volume 3. McGraw-hill New York, 1964.
  36. Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the Bethe Hessian. In Advances in Neural Information Processing Systems , pp. 406-414, 2014.
  37. Mohamed El Amine Seddik, Mohamed Tamaazousti, and Romain Couillet. A kernel random matrixbased approach for sparse PCA. In International Conference on Learning Representations , 2018.
  38. Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random matrix theory proves that deep learning representations of GAN-data behave as gaussian mixtures. arXiv preprint arXiv:2001.08370 , 2020. · arXiv
  39. Sheng Shen, Zhen Dong, Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Q-BERT: Hessian Based Ultra Low Precision Quantization of BERT. In AAAI , pp. 8815-8821, 2020.
  40. Jack W Silverstein and ZD Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices. Journal of Multivariate analysis , 54(2):175-192, 1995.
  41. Jack W Silverstein and Sang-Il Choi. Analysis of the limiting spectral distribution of large dimensional random matrices. Journal of Multivariate Analysis , 54(2):295-309, 1995.
  42. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research , 15(1):1929-1958, 2014.
  43. Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition , pp. 1-9, 2015.
  44. Terence Tao, Van Vu, and Manjunath Krishnapur. Random matrices: Universality of ESDs and the circular law. The Annals of Probability , 38(5):2023-2065, 2010.
  45. Dan Voiculescu. Addition of certain non-commuting random variables. Journal of functional analysis , 66(3):323-346, 1986.
  46. Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing , 17(4):395-416, 2007.
  47. Shusen Wang, Fred Roosta, Peng Xu, and Michael W Mahoney. GIANT: Globally improved approximate Newton method for distributed optimization. In Advances in Neural Information Processing Systems , pp. 2332-2342, 2018.
  48. Eugene P. Wigner. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Mathematics , 62(3):548-564, 1955.
  49. Tayeb Zarrouk, Romain Couillet, Florent Chatelain, and Nicolas Le Bihan. Performance-complexity trade-off in large dimensional statistics. In 2020 IEEE International Workshop on Machine Learning for Signal Processing (MLSP) . IEEE, 2020.

Cited by

Sorted by citations

Authors
Liao, Z., Couillet, R., & Mahoney, M. W.
Affiliations
  • University of California, Berkeley (US)
  • Institut polytechnique de Grenoble (FR)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2010.01376
arXiv
2010.01376
OpenAlex
W3090653942
Cited by
10
References
1
Citations by year
2023: 3 · 2022: 4 · 2021: 2 · 2020: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • HAL (submittedVersion, other-oa)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
  • Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
Keywords
spectral clustering, matrix sparsification, random matrix theory, eigenvalue spectrum, nonlinear transformation, phase transitions

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review