Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature

DOI10.1137/16M1104974zbMath1386.65125OpenAlexW2764280570MaRDI QIDQ4588935

Shashanka Ubaru, Yousef Saad, Jie Chen

Publication date: 6 November 2017

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1104974

zbMATH Keywords

Gaussian processesLanczos algorithmSchatten normstrace estimationlog-determinantsfast approximate algorithms

Mathematics Subject Classification ID

Related Items (28)

Randomized numerical linear algebra: Foundations and algorithms ⋮ A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ Data Analytics on Graphs Part III: Machine Learning on Graphs, from Graph Topology to Applications ⋮ 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 ⋮ The Short-Term Rational Lanczos Method and Applications ⋮ A literature survey of matrix methods for data science ⋮ The global Golub-Kahan method and Gauss quadrature for tensor function approximation ⋮ Krylov-Aware Stochastic Trace Estimation ⋮ Linear-Cost Covariance Functions for Gaussian Random Fields ⋮ Randomized Low-Rank Approximation of Monotone Matrix Functions ⋮ XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation ⋮ Numerical solution of a class of quasi-linear matrix equations ⋮ 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 ⋮ FANOK: Knockoffs in Linear Time ⋮ Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten \(p\)-norms ⋮ Shifted extended global Lanczos processes for trace estimation with application to network analysis ⋮ Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions ⋮ Locally induced Gaussian processes for large-scale simulation experiments ⋮ Efficient Covariance Approximations for Large Sparse Precision Matrices ⋮ A multilevel approach to stochastic trace estimation ⋮ Kryging: geostatistical analysis of large-scale datasets using Krylov subspace methods ⋮ Error Bounds for Lanczos-Based Matrix Function Approximation ⋮ Interpolating log-determinant and trace of the powers of matrix \(\mathbf{A}+ t\mathbf{B}\)

Uses Software

• SparseMatrix
• GMRFLib
• Krylstat
• mftoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth function topological structure descriptors based on graph-spectra
• Improved bounds on sample size for implicit matrix trace estimators
• Parameter estimation in high dimensional Gaussian distributions
• Estimates in quadratic formulas
• 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
• 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
• A new status index derived from sociometric analysis
• Exact matrix completion via convex optimization
• Approximating Spectral Densities of Large Matrices
• Matrix Inverse Trigonometric and Inverse Hyperbolic Functions: Theory and Algorithms
• How Accurately Should I Compute Implicit Matrix-Vector Products When Applying the Hutchinson Trace Estimator?
• Sketching and Embedding are Equivalent for Norms
• 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
• Computing $f(A)b$ via Least Squares Polynomial Approximations
• Approximate implementation of the logarithm of the matrix determinant in Gaussian process regression
• Computing $A^\alpha, \log(A)$, and Related Matrix Functions by Contour Integrals
• Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
• Log-determinant relaxation for approximate inference in discrete Markov random fields
• Gaussian Markov Random Fields
• Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• On Sketching Matrix Norms and the Top Singular Vector
• Functions of Matrices
• Rough and ready error estimates in Gaussian integration of analytic functions
• Calculation of Gauss Quadrature Rules
• Calculating the Singular Values and Pseudo-Inverse of a Matrix
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines

This page was built for publication: Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature