Editing Trace (linear algebra) (section)

=== Stochastic estimator ===
The trace can be estimated unbiasedly by "Hutchinson's trick":<ref>{{Cite journal |last=Hutchinson |first=M.F. |date=January 1989 |title=A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines |url=http://www.tandfonline.com/doi/abs/10.1080/03610918908812806 |journal=Communications in Statistics - Simulation and Computation |language=en |volume=18 |issue=3 |pages=1059–1076 |doi=10.1080/03610918908812806 |issn=0361-0918|url-access=subscription }}</ref><blockquote>Given any matrix <math>\boldsymbol W\in \R^{n\times n}</math>, and any random <math>\boldsymbol u\in \R^n</math> with <math>\mathbb E[\boldsymbol u\boldsymbol u^\intercal] = \mathbf I</math>, we have <math>\mathbb E[\boldsymbol u^\intercal\boldsymbol W\boldsymbol u ] = \operatorname{tr}\boldsymbol W</math>. </blockquote>

For a proof expand the expectation directly. 

Usually, the random vector is sampled from <math>\operatorname N(\mathbf 0,\mathbf I)</math> (normal distribution) or <math>\{\pm n^{-1/2}\}^n</math> ([[Rademacher distribution]]).

More sophisticated stochastic estimators of trace have been developed.<ref>{{Cite journal |last1=Avron |first1=Haim |last2=Toledo |first2=Sivan |date=2011-04-11 |title=Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix |url=https://doi.org/10.1145/1944345.1944349 |journal=Journal of the ACM |volume=58 |issue=2 |pages=8:1–8:34 |doi=10.1145/1944345.1944349 |s2cid=5827717 |issn=0004-5411}}</ref>