Spectral Estimation with Free Decompression
Preprint
Abstract
Computing eigenvalues of very large matrices is a critical task in many machine learning applications, including the evaluation of log-determinants, the trace of matrix functions, and other important metrics. As datasets continue to grow in scale, the corresponding covariance and kernel matrices become increasingly large, often reaching magnitudes that make their direct formation impractical or impossible. Existing techniques typically rely on matrix-vector products, which can provide efficient approximations, if the matrix spectrum behaves well. However, in settings like distributed learning, or when the matrix is defined only indirectly, access to the full data set can be restricted to only very small sub-matrices of the original matrix. In these cases, the matrix of nominal interest is not even available as an implicit operator, meaning that even matrix-vector products may not be available. In such settings, the matrix is "impalpable," in the sense that we have access to only masked snapshots of it. We draw on principles from free probability theory to introduce a novel method of "free decompression" to estimate the spectrum of such matrices. Our method can be used to extrapolate from the empirical spectral densities of small submatrices to infer the eigenspectrum of extremely large (impalpable) matrices (that we cannot form or even evaluate with full matrix-vector products). We demonstrate the effectiveness of this approach through a series of examples, comparing its performance against known limiting distributions from random matrix theory in synthetic settings, as well as applying it to submatrices of real-world datasets, matching them with their full empirical eigenspectra.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Random Matrix Methods for Machine Learning2022
- Randomized matrix-free trace and log-determinant estimatorsNumerische Mathematik, 2017
- Error bounds and estimates for Krylov subspace approximations of Stieltjes matrix functionsBIT Numerical Mathematics, 2015
- Law of log determinant of sample covariance matrix and optimal estimation of differential entropy for high-dimensional Gaussian distributionsJournal of Multivariate Analysis, 2015
- Infinite random matrix theory, tridiagonal bordered Toeplitz matrices, and the moment problemLinear Algebra and its Applications, 2015
- Improved Bounds on Sample Size for Implicit Matrix Trace EstimatorsFoundations of Computational Mathematics, 2014
- Free Meixner StatesCommunications in Mathematical Physics, 2007
- Matrices, moments and quadrature II; How to compute the norm of the error in iterative methodsBIT Numerical Mathematics, 1997
- Limit laws for Random matrices and free productsInventiones Mathematicae, 1991
- The expected eigenvalue distribution of a large regular graphLinear Algebra and its Applications, 1981