The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
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( A ). These algorithms are useful in applications in which there is no explicit representation of A but rather an efficient method compute z T Az given z . Existing results only analyze the variance of the different estimators. In contrast, we analyze the number of samples M required to guarantee that with probability at least 1-δ, the relative error in the estimate is at most ϵ. 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
Statistics for experimenters. An introduction to design, data analysis, and model building.
Box, G. E. P., Hunter, W. G., & Hunter, J. S. (1978) · Cited by 4,021
An Introduction to Probability Theory.
Fristedt, B., & Moran, P. A. P. (1986) · Journal of the American Statistical Association · doi:10.2307/2288022 · Cited by 3,300
An Introduction to Probability Theory and Its Applications, Vol. 1
Feller, W. (1968) · Cited by 1,446
An Introduction to Probability Theory and its Applications.
Kendall, D. G., & Feller, W. (1951) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2980979 · Cited by 1,283
Database-friendly random projections
Achlioptas, D. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375608 · Cited by 699
A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
Hutchinson, M. F. (1990) · Communications in Statistics - Simulation and Computation · doi:10.1080/03610919008812866 · Cited by 610
The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
Ailon, N., & Chazelle, B. (2009) · SIAM Journal on Computing · doi:10.1137/060673096 · Cited by 479
A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
Hutchinson, M. F. (1989) · Communications in Statistics - Simulation and Computation · doi:10.1080/03610918908812806 · Cited by 381
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Ailon, N., & Chazelle, B. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132597 · Cited by 379
Cited by
HAWQ-V2: Hessian Aware trace-Weighted Quantization of Neural Networks
Dong, Z., Yao, Z., Cai, Y., Arfeen, D., Gholami, A., Mahoney, M. W., & Keutzer, K. (2019) · arXiv · doi:10.48550/arxiv.1911.03852 · Cited by 110
Quantum algorithms for training Gaussian processes
Zhao, Z., Fitzsimons, J. K., Osborne, M. A., Roberts, S. J., & Fitzsimons, J. F. (2019) · Physical Review A · doi:10.1103/physreva.100.012304 · Cited by 19
A Novel Mixed-Precision Quantization Approach for CNNs
Wu, D., Wang, Y., Fei, Y., & Gao, G. (2025) · IEEE Access · doi:10.1109/access.2025.3551802 · Cited by 8
Metadata
- Authors
- Avron, H., & Toledo, S.
- Venue
- Journal of the ACM
- Published
- 2011-04
- Volume
- 58
- Issue
- 2
- Pages
- 1-34
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2057450058
- Cited by
- 284
- References
- 17
- FWCI
- 6.58
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. https://app.cochat.ai/papers/10.1145/1944345.1944349
- The paper
- Avron, H., & Toledo, S. (2011). Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Journal of the ACM. https://doi.org/10.1145/1944345.1944349
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.