Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix

By Haim Avron, Sivan Toledo. 2011

409 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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 Mechanics

In Statistics and Probability

Citations in the corpus

There Are Many Consistent Explanations of Unlabeled Data: Why You Should Average (2018, background): “We can now recognize this term as a one sample stochastic trace estimator for tr(J(xi)TJ(xi)) with a Gaussian probe variable zi; see Avron and Toledo (2011) for derivations and guarantees on stochastic trace estimators.”
Estimating the Spectral Density of Large Implicit Matrices (2018, methodology): “Avron and Toledo (2011) also studied theoretical properties of the trace estimator, and developed convergence bounds, later extended by Roosta-Khorasani and Ascher (2015).”
G-DAug: Generative Data Augmentation for Commonsense Reasoning (2020, methodology): “, 2019), we compute the Hessian trace of 10 baseline and 10 G-DAUG-Combo methods using the Hutchinson Method (Avron and Toledo, 2011) and find a relative decrease of 9.”
How to train your neural ODE (2020, methodology): “In trace form, the Frobenius norm lends itself to estimation using a Monte-Carlo trace estimator (Hutchinson, 1990; Avron & Toledo, 2011).”
A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix (2015, methodology): “For situations such as these, Avron and Toledo [1] analyzed several algorithms to estimate the trace of A .”
Stochastic Chebyshev Gradient Descent for Spectral Optimization (2018, background): “From [13, 4], we have that Varv[vAv] = 2(‖A‖2F − ∑d i=1A 2 ii) ≤ 2 ‖A‖ 2 F and Ev[v >Gv] = tr (G) for Rademacher random vector v ∈ [−1, 1] and A ∈ Sd×d.”
Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature (2017, background): “Strictly speaking, the prior results [5, 38] on which our bounds in section 4 are based, compute the approximation as ‖ul‖(2)2 · v> l f(A)vl, rather than n · v> l f(A)vl.”
Stein Unbiased GrAdient estimator of the Risk (SUGAR) for Multiple Parameter Selection (2014, background): “Remark that ∆ does not necessary have to be Gaussian and higher precisions can be reached in some specific cases, see for instance [1, 21, 39, 58].”
OT-Flow: Fast and Accurate Continuous Normalizing Flows via Optimal Transport (2020, methodology): “We use the exact trace; however, if we wanted to use a trace estimate, a plethora of estimators perform better in accuracy and speed on symmetric matrices than on nonsymmetric matrices (Hutchinson 1990; Avron and Toledo 2011; Ubaru, Chen, and Saad 2017).”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “PYHESSIAN computes Hessian information by applying known techniques from Numerical Linear Algebra (NLA) [4, 10, 17] and Randomized NLA (RandNLA) [3, 7, 8, 18, 25, 27] (that are approximate but come with rigorous theory).”
GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration (2018, background): “Estimating Tr(K̂−1 XX ∂K̂XX ∂θ ) from CG relies on stochastic trace estimation [3, 14, 25], which allows us to treat this term as a sum of linear solves.”
Approximating Spectral Densities of Large Matrices (2013, positive): “The stochastic sampling and averaging technique is based on the following key result [18, 36, 2].”
Backpropagation for Implicit Spectral Densities (2018, methodology): “We refer the reader to Avron and Toledo [2011] for a detailed study on the variance of this estimator.”
Scalable Log Determinants for Gaussian Process Kernel Learning (2017, background): “If ˜ K = U Λ U T + σ 2 I , the Hutchinson trace estimator has known variance [39] Var If the eigenvalues of the kernel matrix without noise decay rapidly enough compared to σ , the variance will be small compared to the magnitude of tr(log ˜ K ) = 2 n log σ + =1 log(1 + λ j /σ 2 ) .”
Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations (2016, background): “In addition, recent progress on analyzing stochastic trace estimation [4, 39] allow us to provide rigorous bounds for the entire procedure.”
HAWQ-V2: Hessian Aware trace-Weighted Quantization of Neural Networks (2019, methodology): “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.”