Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations

DOI10.1137/16M1078148zbMath1372.65126arXiv1606.00942OpenAlexW2750001921MaRDI QIDQ5350223

Dmitry M. Malioutov, Jinwoo Shin, Insu Han, Haim Avron

Publication date: 28 August 2017

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.00942

zbMATH Keywords

algorithmspectral functionSchatten \(p\)-normEstrada indexChebyshev approximationmatrix computationnumerical expampleslog-determinantHutchinson's methodtrace of matrix functions

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of matrix exponential and similar matrix functions (65F60)

Related Items

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness, 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, A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix, Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature, Krylov-Aware Stochastic Trace Estimation, Linear-Cost Covariance Functions for Gaussian Random Fields, Solving trust region subproblems using Riemannian optimization, Conditional gradient method for double-convex fractional programming matrix problems, A general scheme for log-determinant computation of matrices via stochastic polynomial approximation, Faster stochastic trace estimation with a Chebyshev product identity, 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, Unnamed Item

Uses Software

• SparseMatrix
• GMRFLib
• QUIC
• Krylstat

Cites Work

• Smooth function topological structure descriptors based on graph-spectra
• Error bounds for approximation in Chebyshev points
• Improved bounds on sample size for implicit matrix trace estimators
• Parameter estimation in high dimensional Gaussian distributions
• Bounds for norms of the matrix inverse and the smallest singular value
• Chebyshev approximation of log-determinants of spatial weight matrices
• Random matrices: The distribution of the smallest singular values
• Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
• Accelerating data uncertainty quantification by solving linear systems with multiple right-hand sides
• An estimator for the diagonal of a matrix
• Estimating the Estrada index
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
• Stochastic approximation of score functions for Gaussian processes
• Some large-scale matrix computation problems
• How Accurately Should I Compute Implicit Matrix-Vector Products When Applying the Hutchinson Trace Estimator?
• Hierarchical Probing for Estimating the Trace of the Matrix Inverse on Toroidal Lattices
• Efficient estimation of eigenvalue counts in an interval
• The university of Florida sparse matrix collection
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Uncertainty Quantification and Weak Approximation of an Elliptic Inverse Problem
• Approximate implementation of the logarithm of the matrix determinant in Gaussian process regression
• Computing an Eigenvector with Inverse Iteration
• Log-determinant relaxation for approximate inference in discrete Markov random fields
• Barycentric Lagrange Interpolation
• Gaussian Markov Random Fields
• Functions of Matrices
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item