Some large-scale matrix computation problems

By Zhong-Zhi Bai, Mark R. Fahey, Gene H. Golub. 1996

Abstract There are numerous applications in physics, statistics and electrical circuit simulation where it is required to bound entries and the trace of the inverse and the determinant of a large sparse matrix. All these computational tasks are related to the central mathematical problem studied in this paper, namely, bounding the bilinear form u T f(A) v for a given matrix A and vectors u and v , where f is a given smooth function and is defined on the spectrum of A. We will study a practical numerical algorithm for bounding the bilinear form, where the matrix A is only referenced through matrix-vector multiplications. A Monte Carlo method is also presented to efficiently estimate the trace of the inverse and the determinant of a large sparse matrix.

Subfields: Optimization & Training

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

An Investigation into Neural Net Optimization via Hessian Eigenvalue Density (2019, methodology): “The underlying algorithm is extremely elegant, and has been known in the numerical analysis literature for decades (Bai et al., 1996) (based on foundational work by Golub and Welsch (1969)); here we introduce it to the machine learning community, and build (and release) a system to run it at modern ”
Emergence of Invariance and Disentanglement in Deep Representations (2017, background): “Efforts to develop a theoretical framework for representation learning include Tishby and Zaslavsky (2015) and Shwartz-Ziv and Tishby (2017), who consider representations as stochastic functions that approximate minimal sufficient statistics, different from Bruna and Mallat (2011) who construct repr”
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix (2011, methodology): “Explicitly computing f (A) for large matrices is not practical, but computing the bilinear form xT f (A)x for an arbitrary x is feasible [Bai et al. 1996, 1998].”
Early Stopping is Nonparametric Variational Inference (2015, methodology): “This is a much harder problem since the Hessian can be arbitrarily ill-conditioned, unlike our small Hessian-based perturbation to the identity.”
A restarted Lanczos approximation to functions of a symmetric matrix (2010, methodology): “Statistical methods for spatial data and other complex structures require f(A) = A−1, f(A) = A 1 2 , f(A) = A− 1 2 [16].”
Modeling, Inference and Optimization With Composable Differentiable Procedures (2016, background): “The trace of the Hessian can be estimated using inner products of random vectors [6]:”
Bounds for eigenvalues of matrix polynomials (2003, methodology): “We note that if A0, Am−1 and Am are symmetric positive definite, then these bounds can be estimated relatively cheaply using Gaussian quadrature and Monte Carlo techniques from [2,3].”
A probing method for computing the diagonal of a matrix inverse (2012, methodology): “This approach is developed by Golub and collaborators, see, e.g. [4, 20, 21], and is described in detail in the book by Golub and Meurant [7].”
Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature (2017, methodology): “The problem of estimating the trace of matrix functions appears frequently in applications of machine learning, signal processing, scientific computing, statistics, computational biology, and computational physics [6, 17, 39, 37, 20, 30, 33, 2, 26].”
Eigenfunction properties and approximations of selected incidence matrices employed in spatial analyses (2000, background): “, [3,5]), a number of analytical results are reported in this paper.”
HAWQ-V2: Hessian Aware trace-Weighted Quantization of Neural Networks (2019, unknown): “In particular, the seminar works of [2, 3] have proposed randomized algorithms for fast trace estimation, using so-called matrix-free methods which do not require the explicit formation of the Hessian operator.”
THE INTERPLAY BETWEEN CLASSICAL ANALYSIS AND (NUMERICAL) LINEAR ALGEBRA — A TRIBUTE TO GENE H. GOLUB (2002, background): “[10, 2 ]). This requires knowledge of the moments of , which by (5.13) are given by”
Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations (2016, background): “Bai et al. [5] were the first to consider the problem of approximating spectral sums, and its specific use for approximating the log-determinant and the trace of the matrix inverse.”
DECAY BOUNDS AND ( ) ALGORITHMS FOR APPROXIMATING FUNCTIONS OF SPARSE MATRICES (2007, methodology): “For instance, when f is analytic, f(A) can be defined by a power series expansion, or by a contour integral (using Cauchy’s Theorem).”