# Spectral Estimation with Free Decompression

arXiv: https://arxiv.org/abs/2506.11994 · HTML: https://mlsanity.com/paper/2506.11994/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 76 references that are in the map.
- First posted on arXiv 13 Jun 2025.

## Builds on (most cited first, 24 of 24)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [AI and Memory Wall](https://mlsanity.com/paper/2403.14123/) (2024)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Fast Finite Width Neural Tangent Kernel](https://mlsanity.com/paper/2206.08720/) (2022)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Estimating the Spectral Density of Large Implicit Matrices](https://mlsanity.com/paper/1802.03451/) (2018)
- [The Interpolating Information Criterion for Overparameterized Models](https://mlsanity.com/paper/2307.07785/) (2023)
- [Monotonicity and Double Descent in Uncertainty Estimation with Gaussian Processes](https://mlsanity.com/paper/2210.07612/) (2022)
- [Uncertainty Quantification with the Empirical Neural Tangent Kernel](https://mlsanity.com/paper/2502.02870/) (2025)
- [Stochastic Marginal Likelihood Gradients using Neural Tangent Kernels](https://mlsanity.com/paper/2306.03968/) (2023)
- [Scale-invariant Bayesian Neural Networks with Connectivity Tangent Kernel](https://mlsanity.com/paper/2209.15208/) (2022)
- [CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra](https://mlsanity.com/paper/2309.03060/) (2023)
- [A PAC-Bayesian Perspective on the Interpolating Information Criterion](https://mlsanity.com/paper/2311.07013/) (2023)
- [Determinant Estimation under Memory Constraints and Neural Scaling Laws](https://mlsanity.com/paper/2503.04424/) (2025)
- [Lecture Notes on Spectral Graph Methods](https://mlsanity.com/paper/1608.04845/) (2016)
- [Improved Spectral Density Estimation via Explicit and Implicit Deflation](https://mlsanity.com/paper/2410.21690/) (2024)
- [Assessing Quantum Advantage for Gaussian Process Regression](https://mlsanity.com/paper/2505.22502/) (2025)

## Built on by (most cited first, 1 of 1)

- [Why Heavy-Tailed Weight Spectra Predict Model Quality](https://mlsanity.com/paper/2610.13123/) (2026)

## Abstract (arXiv)

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.