Name
Abstract | ||
|---|---|---|
This article is concerned with Monte Carlo methods for the estimation of the trace of an implicitly given matrix $$A$$A whose information is only available through matrix-vector products. Such a method approximates the trace by an average of $$N$$N expressions of the form $$ \\mathbf{w} ^t (A \\mathbf{w} )$$wt(Aw), with random vectors $$ \\mathbf{w} $$w drawn from an appropriate distribution. We prove, discuss and experiment with bounds on the number of realizations $$N$$N required to guarantee a probabilistic bound on the relative error of the trace estimation upon employing Rademacher (Hutchinson), Gaussian and uniform unit vector (with and without replacement) probability distributions. In total, one necessary bound and six sufficient bounds are proved, improving upon and extending similar estimates obtained in the seminal work of Avron and Toledo (JACM 58(2). Article 8, 2011) in several dimensions. We first improve their bound on $$N$$N for the Hutchinson method, dropping a term that relates to $$\\mathrm{rank}(A)$$rank(A) and making the bound comparable with that for the Gaussian estimator. We further prove new sufficient bounds for the Hutchinson, Gaussian and unit vector estimators, as well as a necessary bound for the Gaussian estimator, which depend more specifically on properties of matrix $$A$$A. As such, they may suggest the type of matrix for which one distribution or another provides a particularly effective or relatively ineffective stochastic estimation method. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10208-014-9220-1 | Foundations of Computational Mathematics |
Keywords | Field | DocType |
Randomized algorithms,Trace estimation,Monte Carlo methods,Implicit linear operators,65C20,65C05,68W20 | Randomized algorithm,Combinatorics,Monte Carlo method,Mathematical optimization,Mathematical analysis,Matrix (mathematics),Gaussian,Probability distribution,Trace (linear algebra),Mathematics,Estimator,Unit vector | Journal |
Volume | Issue | ISSN |
abs/1308.2475 | 5 | 1615-3375 |
Citations | PageRank | References |
27 | 1.18 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Farbod Roosta-Khorasani | 1 | 102 | 9.25 |
| Uri M. Ascher | 2 | 375 | 113.62 |