Research map / Learning theory and algorithms / Matrix and tensor methods
Free Decompression with Algebraic Spectral Curves
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.
Extends free decompression to matrices whose Stieltjes transform is algebraic, implementing a polynomial-method framework (FDPM) that traces spectral curves to expand multi-bulk, multi-scale, and atomic spectra of ML matrices.
Problem
Free decompression, which extrapolates spectral densities from small submatrices to large matrices, is limited to single smooth bulks; realistic ML spectra (multi-bulk, multi-scale, atoms) are not handled.
Approach
Assume the Stieltjes transform is algebraic (root of a bivariate polynomial), fit that polynomial from samples, and recast free decompression as a rational reparameterization/evolution along the spectral curve, tracked by predictor-corrector continuation; atoms, moments, edges and bulk splits follow from the curve in closed form.
Key results
- On the diffusion-model random-feature matrix, FD on a 4K submatrix plus evolution to 64K took 32.2 s + 6.8 s versus 192447.7 s for direct eigendecomposition at 64K size.
- At 64K, FD achieved W1/L of 2.19% and MMD of 0.53% against the empirical spectrum, with mean log-edge error 0.4%.
- FD on the compound free Poisson example recovered atom dynamics and bulk splitting from a 1000x1000 submatrix to 6000x6000 size.
Limitations
- Heavy-tailed spectral distributions remain difficult with current tools.
- Finite-size edge correction may need refinement for extreme near-singular edges.
- The free decompression theorem may require unitary invariance for general matrices.
Experimental setup
Datasets: CIFAR-10
Benchmarks: compound free Poisson spectrum (6000x6000) neural network Hessian (32768x32768) random-features diffusion activation matrix (64000x64000)
Metrics: Wasserstein-1 distance on log-eigenvalues MMD relative error of moments log edge error process time
Baselines: direct eigendecomposition
Builds on: free decompression polynomial method Nica-Speicher theorem
Closest papers by meaning
- Spectral Estimation with Deformed Decompression (NeurIPS 2026 · similarity 0.90)
- Spectral Estimation with Free Decompression (NeurIPS 2025 · similarity 0.90)
- Random Matrix Theory of Early-Stopped Gradient Flow: A Transient BBP Scenario (NeurIPS 2026 · similarity 0.87)
- Optimal Spectral Transitions in High-Dimensional Multi-Index Models (NeurIPS 2025 · similarity 0.86)
- Learning to Discover Iterative Spectral Algorithms (NeurIPS 2026 · similarity 0.86)
- Out of the Ordinary: Spectrally Adapting Regression for Covariate Shift (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.