Access Restriction

Author Avron, Haim ♦ Toledo, Sivan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Trace estimation ♦ Implicit linear operators
Abstract We analyze the convergence of randomized trace estimators. Starting at 1989, several algorithms have been proposed for estimating the trace of a matrix by $1/M∑_{i}=1^{M}$ $z_{i}^{T}$ $Az_{i},$ where the $z_{i}$ are random vectors; different estimators use different distributions for the $z_{i}s,$ all of which lead to $E(1/M∑_{i}=1^{M}$ $z_{i}^{T}$ $Az_{i})$ = $trace(\textit{A}).$ These algorithms are useful in applications in which there is no explicit representation of $\textit{A}$ but rather an efficient method compute $z^{T}Az$ given $\textit{z}.$ Existing results only analyze the variance of the different estimators. In contrast, we analyze the number of samples $\textit{M}$ required to guarantee that with probability at least 1™Δ, the relative error in the estimate is at most &epsis;. We argue that such bounds are much more useful in applications than the variance. We found that these bounds rank the estimators differently than the variance; this suggests that minimum-variance estimators may not be the best. We also make two additional contributions to this area. The first is a specialized bound for projection matrices, whose trace (rank) needs to be computed in electronic structure calculations. The second is a new estimator that uses less randomness than all the existing estimators.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-04-11
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 58
Issue Number 2
Page Count 34
Starting Page 1
Ending Page 34

Open content in new tab

   Open content in new tab
Source: ACM Digital Library