{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T02:40:17Z","timestamp":1782614417964,"version":"3.54.5"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,4,1]],"date-time":"2011-04-01T00:00:00Z","timestamp":1301616000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","award":["1045\/09"],"award-info":[{"award-number":["1045\/09"]}],"id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p>\n            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\u03a3\n            <jats:sub>i<\/jats:sub>\n            =1\n            <jats:sup>M<\/jats:sup>\n            z\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:sup>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>Az<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            , where the\n            <jats:italic>z<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            are random vectors; different estimators use different distributions for the\n            <jats:italic>z<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            s, all of which lead to\n            <jats:italic>E<\/jats:italic>\n            (1\/M\u03a3\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            =1\n            <jats:sup>\n              <jats:italic>M<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>z<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:sup>T<\/jats:sup>\n            <jats:italic>Az<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            ) = trace(\n            <jats:italic>A<\/jats:italic>\n            ). These algorithms are useful in applications in which there is no explicit representation of\n            <jats:italic>A<\/jats:italic>\n            but rather an efficient method compute\n            <jats:italic>z<\/jats:italic>\n            <jats:sup>T<\/jats:sup>\n            <jats:italic>Az<\/jats:italic>\n            given\n            <jats:italic>z<\/jats:italic>\n            . Existing results only analyze the variance of the different estimators. In contrast, we analyze the number of samples\n            <jats:italic>M<\/jats:italic>\n            required to guarantee that with probability at least 1-\u03b4, the relative error in the estimate is at most \u03f5. 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.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1944345.1944349","type":"journal-article","created":{"date-parts":[[2011,4,12]],"date-time":"2011-04-12T12:03:38Z","timestamp":1302609818000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":212,"title":["Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix"],"prefix":"10.1145","volume":"58","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv and IBM T.J. Watson Research Center, Yorktown Heights, NY"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,4,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375608"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958627.1958633"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(96)00018-0"},{"key":"e_1_2_1_5_1","unstructured":"Bai Z. Fahey M. Golub G. Menon M. and Richter E. 1998. Computing partial eigenvalue sum in electronic structure calculations. Tech. rep. SCCM-98-03 Stanford University.  Bai Z. Fahey M. Golub G. Menon M. and Richter E. 1998. Computing partial eigenvalue sum in electronic structure calculations. Tech. rep. SCCM-98-03 Stanford University."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2007.01.003"},{"key":"e_1_2_1_7_1","unstructured":"Box G. E. P. Hunter W. G. and Hunter J. S. 1978. Statistics for Experimenters: An Introduction to Design Data Analysis and Model Building. Wiley &amp;amp; Sons.  Box G. E. P. Hunter W. G. and Hunter J. S. 1978. Statistics for Experimenters: An Introduction to Design Data Analysis and Model Building. Wiley &amp;amp; Sons."},{"key":"e_1_2_1_8_1","unstructured":"D'Elia M. Haber H. and Horesh L. 2011. Design of proper orthogonal decomposition bases by means of stochastic optimization. To be submitted.  D'Elia M. Haber H. and Horesh L. 2011. Design of proper orthogonal decomposition bases by means of stochastic optimization. To be submitted."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.70.3631"},{"key":"e_1_2_1_10_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller W.","unstructured":"Feller , W. 1971. An Introduction to Probability Theory and Its Applications , Vol. 2 , 3rd. Ed. Wiley . Feller, W. 1971. An Introduction to Probability Theory and Its Applications, Vol. 2, 3rd. Ed. Wiley."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893243876"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.057701"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1208358889"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595282519"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Li P. Hastie T. and \n      Church K\n  . \n  2007\n  . Nonlinear estimators and tail bounds for dimension reduction in l<sub>1<\/sub> using Cauchy random projections. In Learning Theory Lecture Notes in Computer Science Series Vol. \n  4539\n  . \n  Springer Berlin Chap. 37 514--529.   Li P. Hastie T. and Church K. 2007. Nonlinear estimators and tail bounds for dimension reduction in l<sub>1<\/sub> using Cauchy random projections. In Learning Theory Lecture Notes in Computer Science Series Vol. 4539. Springer Berlin Chap. 37 514--529.","DOI":"10.1007\/978-3-540-72927-3_37"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.56.4822"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706095"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.49.10154"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.6.4380"},{"key":"e_1_2_1_22_1","unstructured":"Wong M. N. Hickernell F. J. and Liu K. I. 2004. Computing the trace of a function of a sparse matrix via Hadamard-like sampling. Tech rep. 377(7\/04) Hong Kong Baptist University.  Wong M. N. Hickernell F. J. and Liu K. I. 2004. Computing the trace of a function of a sparse matrix via Hadamard-like sampling. Tech rep. 377(7\/04) Hong Kong Baptist University."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1944345.1944349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:30Z","timestamp":1750244370000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944345.1944349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1145\/1944345.1944349"],"URL":"https:\/\/doi.org\/10.1145\/1944345.1944349","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]},"assertion":[{"value":"2010-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}