Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
From MaRDI portal
Abstract: Computation of the trace of a matrix function plays an important role in many scientific computing applications, including applications in machine learning, computational physics (e.g., lattice quantum chromodynamics), network analysis and computational biology (e.g., protein folding), just to name a few application areas. We propose a linear-time randomized algorithm for approximating the trace of matrix functions of large symmetric matrices. Our algorithm is based on coupling function approximation using Chebyshev interpolation with stochastic trace estimators (Hutchinson's method), and as such requires only implicit access to the matrix, in the form of a function that maps a vector to the product of the matrix and the vector. We provide rigorous approximation error in terms of the extremal eigenvalue of the input matrix, and the Bernstein ellipse that corresponds to the function at hand. Based on our general scheme, we provide algorithms with provable guarantees for important matrix computations, including log-determinant, trace of matrix inverse, Estrada index, Schatten p-norm, and testing positive definiteness. We experimentally evaluate our algorithm and demonstrate its effectiveness on matrices with tens of millions dimensions.
Recommendations
- Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
- Randomized matrix-free trace and log-determinant estimators
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- Randomized estimation of spectral densities of large matrices made accurate
- Estimating the trace of matrix functions with application to complex networks
Cites work
- A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
- A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
- Accelerating data uncertainty quantification by solving linear systems with multiple right-hand sides
- An estimator for the diagonal of a matrix
- Approximate implementation of the logarithm of the matrix determinant in Gaussian process regression
- Approximation theory and approximation practice
- Barycentric Lagrange Interpolation
- Bounds for norms of the matrix inverse and the smallest singular value
- Chebyshev approximation of log-determinants of spatial weight matrices
- Computing an Eigenvector with Inverse Iteration
- Efficient estimation of eigenvalue counts in an interval.
- Error bounds for approximation in Chebyshev points
- Estimating the Estrada index
- Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
- Functions of Matrices
- Gaussian Markov Random Fields
- Gaussian processes for machine learning.
- Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices
- How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?
- scientific article; zbMATH DE number 1256751 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 6256254 (Why is no real title available?)
- Improved bounds on sample size for implicit matrix trace estimators
- Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
- Log-determinant relaxation for approximate inference in discrete Markov random fields
- Parameter estimation in high dimensional Gaussian distributions
- Random matrices: The distribution of the smallest singular values
- Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
- Smooth function topological structure descriptors based on graph-spectra
- Some large-scale matrix computation problems
- Stochastic approximation of score functions for Gaussian processes
- The University of Florida sparse matrix collection
- Uncertainty Quantification and Weak Approximation of an Elliptic Inverse Problem
Cited in
(29)- Conditional gradient method for double-convex fractional programming matrix problems
- A general scheme for log-determinant computation of matrices via stochastic polynomial approximation
- Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten p-norms
- Randomized block Krylov subspace methods for trace and log-determinant estimators
- A multilevel approach to stochastic trace estimation
- Interpolating log-determinant and trace of the powers of matrix \(\mathbf{A}+ t\mathbf{B}\)
- Faster stochastic trace estimation with a Chebyshev product identity
- A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
- On randomized trace estimates for indefinite matrices with an application to determinants
- Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
- Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
- scientific article; zbMATH DE number 7049740 (Why is no real title available?)
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
- Krylov-Aware Stochastic Trace Estimation
- Linear-Cost Covariance Functions for Gaussian Random Fields
- Solving trust region subproblems using Riemannian optimization
- Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
- Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methods
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- A Fast Monte Carlo Algorithm for Evaluating Matrix Functions with Application in Complex Networks
- Faster randomized partial trace estimation
- The computational advantage of MIP* vanishes in the presence of noise
- The computational advantage of MIP* vanishes in the presence of noise
- Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
- Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
- Two Gaussian regularization methods for time-varying networks
- Multivariate trace estimation using quantum state space linear algebra
- Chebyshev approximation of log-determinants of spatial weight matrices
This page was built for publication: Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5350223)
