Skip to yearly menu bar Skip to main content


Asynchronous Randomized Trace Estimation

Vasileios Kalantzis · Shashanka Ubaru · Chai Wah Wu · Georgios Kollias · Lior Horesh

MR1 & MR2 - Number 43
[ ]
Thu 2 May 8 a.m. PDT — 8:30 a.m. PDT

Abstract: Randomized trace estimation is a popular technique to approximate the trace of an implicitly-defined matrix $A$ by averaging the quadratic form $x'Ax$ across several samples of a random vector $x$. This paper focuses on the application of randomized trace estimators on asynchronous computing environments where the quadratic form $x'Ax$ is computed partially by observing only a random row subset of $A$ for each sample of the random vector $x$. Our asynchronous framework treats the number of rows, as well as the row subset observed for each sample, as random variables, and our theoretical analysis establishes the variance of the randomized estimator for Rademacher and Gaussian samples. We also present error analysis and sampling complexity bounds for the proposed asynchronous randomized trace estimator. Our numerical experiments illustrate that the asynchronous variant can be competitive even when a small number of rows is updated per each sample.

Live content is unavailable. Log in and register to view live content