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

Access Restriction
Subscribed

 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

Source: ACM Digital Library