Spectral Estimation with Free Decompression

• URL: http://arxiv.org/abs/2506.11994v1
• Date: Fri, 13 Jun 2025 17:49:25 GMT
• Title: Spectral Estimation with Free Decompression
• Authors: Siavash Ameli, Chris van der Heide, Liam Hodgkinson, Michael W. Mahoney,
• Abstract summary: We introduce a novel method of "free decompression" to estimate the spectrum of very large (impalpable) matrices.<n>Our method can be used to extrapolate from the empirical spectral densities of small submatrices to infer the eigenspectrum of extremely large (impalpable) matrices.
• Score: 47.81955761814048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Infinitesimal Higher-Order Spectral Variations in Rectangular Real Random Matrices [0.0]
  We present a theoretical framework for deriving the general $n$-th order Fr'echet derivatives of singular values in real rectangular matrices.<n>We leverage reduced resolvent operators from Kato's perturbation analytic theory for self-adjoint operators.<n>Our framework equips researchers with a practical toolkit for higher-order spectral sensitivity studies in random matrix applications.
  arXiv  Detail & Related papers  (2025-06-04T09:28:35Z)
• Perturbation Analysis of Singular Values in Concatenated Matrices [0.0]
  How does the singular value spectrum and singular perturbationd matrix relate to the spectra of its individual components?<n>We setup analytical bounds that quantify stability of values under small perturbations in submatrices.<n>Results demonstrate that if submatrices are close in a norm, dominant singular values of the singular matrix remain stable enabling controlled trade-offs between accuracy and compression.
  arXiv  Detail & Related papers  (2025-03-11T09:28:57Z)
• Fast Spectrum Estimation of Some Kernel Matrices [0.0]
  We introduce a new eigenvalue quantile estimation framework for some kernel matrices. This framework gives meaningful bounds for all the eigenvalues of a kernel matrix while avoiding the cost of constructing the full matrix. We prove the efficacy of this framework given certain bounds on the kernel function, and we provide empirical evidence for its accuracy.
  arXiv  Detail & Related papers  (2024-11-01T15:19:54Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Multiresolution kernel matrix algebra [0.0]
  We show the compression of kernel matrices by means of samplets produces optimally sparse matrices in a certain S-format. The inverse of a kernel matrix (if it exists) is compressible in the S-format as well. The matrix algebra is justified mathematically by pseudo differential calculus.
  arXiv  Detail & Related papers  (2022-11-21T17:50:22Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
  We consider an adversarially-trained version of the nonnegative matrix factorization. In our formulation, an attacker adds an arbitrary matrix of bounded norm to the given data matrix. We design efficient algorithms inspired by adversarial training to optimize for dictionary and coefficient matrices.
  arXiv  Detail & Related papers  (2021-04-10T13:13:17Z)
• On Random Matrices Arising in Deep Neural Networks: General I.I.D. Case [0.0]
  We study the distribution of singular values of product of random matrices pertinent to the analysis of deep neural networks. We use another, more streamlined, version of the techniques of random matrix theory to generalize the results of [22] to the case where the entries of the synaptic weight matrices are just independent identically distributed random variables with zero mean and finite fourth moment.
  arXiv  Detail & Related papers  (2020-11-20T14:39:24Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.