Research map / Learning theory and algorithms / Matrix and tensor methods

Spectral Estimation with Deformed Decompression

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces free decompression, a PDE-based method (via free probability and the R-transform) that extrapolates the spectral density of a large impalpable matrix from the eigenvalues of a small random submatrix, with a Python package freealg.

Problem

Estimating the eigenspectrum (empirical spectral density) of very large matrices that cannot be formed or accessed via matrix-vector products, where only small submatrices are available.

Approach

Uses free compression in reverse: the R-transform of a small submatrix is scaled by the decompression ratio n/n_s, equivalently the Stieltjes transform evolves under a first-order quasilinear PDE solved by characteristics, with an analytic continuation (gluing function) to the second sheet to handle the support cut.

Key results

• On the NTK matrix, free decompression from a 2048x2048 submatrix to 50000x50000 gave TV distance 2.9% and JS divergence 5.5% with 2.4% relative error in first moment.
• For Marchenko-Pastur extrapolation to n=32000 averaged over ten matrices, mean TV distance was 0.2% and log-determinant relative error 1.78%.
• Free decompression runtime for the NTK at 50K was about 16 s after a 10.2 s base cost, versus 67331 s for direct computation.

Surprising findings

• Free decompression wall-clock cost on the NTK stays nearly constant as target size grows, while direct computation scales to tens of thousands of seconds.

Limitations

• Accuracy depends strongly on the quality of the spectral density estimate of the submatrix and on the gluing function approximation.
• Becomes delicate on real data compared to synthetic cases.
• Highly ill-conditioned matrices remain difficult without estimating the Stieltjes transform on log scale.

Experimental setup

Datasets: SNAP Facebook Page-Page network CIFAR-10 synthetic Wishart/random matrix ensembles

Benchmarks: Marchenko-Pastur law Wigner semicircle Kesten-McKay Wachter Meixner SNAP Facebook Page-Page Laplacian spectrum empirical NTK of ResNet-50 on CIFAR-10

Metrics: total variation distance Jensen-Shannon divergence relative error in first and second moments log-determinant runtime

Baselines: Nystrom method direct eigendecomposition of the full matrix Marchenko-Pastur law (analytic)

Builds on: free compression (Nica-Speicher) stochastic Lanczos quadrature Nystrom method FLODANCE

Closest papers by meaning

• Spectral Estimation with Free Decompression (NeurIPS 2025 · similarity 0.91)
• Free Decompression with Algebraic Spectral Curves (NeurIPS 2026 · similarity 0.90)
• Optimal Spectral Transitions in High-Dimensional Multi-Index Models (NeurIPS 2025 · similarity 0.84)
• Nonlinear Laplacians: Tunable principal component analysis under directional prior information (NeurIPS 2025 · similarity 0.84)
• Perturbation Bounds for Low-Rank Inverse Approximations under Noise (NeurIPS 2025 · similarity 0.84)
• Improving Diffusion Models for Inverse Problems Using Optimal Posterior Covariance (ICML 2024 · similarity 0.84)