Abstract
Computing eigenvalues of very large matrices is a critical task in manymachine learning applications, including the evaluation of log-determinants,the trace of matrix functions, and other important metrics. As datasetscontinue to grow in scale, the corresponding covariance and kernel matricesbecome increasingly large, often reaching magnitudes that make their directformation impractical or impossible. Existing techniques typically rely onmatrix-vector products, which can provide efficient approximations, if thematrix spectrum behaves well. However, in settings like distributed learning,or when the matrix is defined only indirectly, access to the full data set canbe restricted to only very small sub-matrices of the original matrix. In thesecases, the matrix of nominal interest is not even available as an implicitoperator, meaning that even matrix-vector products may not be available. Insuch settings, the matrix is "impalpable," in the sense that we have access toonly masked snapshots of it. We draw on principles from free probability theoryto introduce a novel method of "free decompression" to estimate the spectrum ofsuch matrices. Our method can be used to extrapolate from the empiricalspectral densities of small submatrices to infer the eigenspectrum of extremelylarge (impalpable) matrices (that we cannot form or even evaluate with fullmatrix-vector products). We demonstrate the effectiveness of this approachthrough a series of examples, comparing its performance against known limitingdistributions from random matrix theory in synthetic settings, as well asapplying it to submatrices of real-world datasets, matching them with theirfull empirical eigenspectra.