Approximating Spectral Densities of Large Matrices

By Lin Lin, Y. Saad, Chao Yang. 2013

179 citations recorded by the source corpus.

In physics, it is sometimes desirable to compute the so-called density of states (DOS), also known as the spectral density, of a real symmetric matrix $A$. The spectral density can be viewed as a probability density distribution that measures the likelihood of finding eigenvalues near some point on the real line. The most straightforward way to obtain this density is to compute all eigenvalues of $A$, but this approach is generally costly and wasteful, especially for matrices of large dimension. There exist alternative methods that allow us to estimate the spectral density function at much lower cost. The major computational cost of these methods is in multiplying $A$ with a number of vectors, which makes them appealing for large-scale problems where products of the matrix $A$ with arbitrary vectors are relatively inexpensive. This article defines the problem of estimating the spectral density carefully and discusses how to measure the accuracy of an approximate spectral density. It then surveys a few kno...

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

In Numerical Methods & Scientific Computing

Citations in the corpus

An Investigation into Neural Net Optimization via Hessian Eigenvalue Density (2019, background): “There is an extensive literature regarding estimating the eigenvalues distribution of large matrices (for a small survey, see [20]).”
The Full Spectrum of Deep Net Hessians At Scale: Dynamics with Sample Size (2018, methodology): “The authors of [10] provided implementations for many of the spectrum approximation methods they proposed, including Lanczos, which is our method of choice.”
Estimating the Spectral Density of Large Implicit Matrices (2018, background): “Lin et al. (2016) provides an excellent survey of diﬀerent techniques for estimating the spectral density of a real symmetric matrix using matrix-vector products, including the Chebyshev expansions and kernel smoothing built upon in the present paper.”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “Instead, it is possible to use stochastic methods from RandNLA to extract this information, without explicitly forming the Hessian matrix.”
Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature (2017, methodology): “Lin, Saad, and Yang [34] demonstrated how the Lanczos algorithm can be used to approximately estimate the spectral density (equivalent to the SLQ method).”
The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size. (2018, methodology): “In this work we follow the method proposed in Lin et al. [2016]. This normalization has the benefit of allowing us to set σ to a fixed number, which does not depend on the specific spectrum approximated.”