{"id":1734,"date":"2024-01-28T02:53:09","date_gmt":"2024-01-28T02:53:09","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1734"},"modified":"2024-01-28T02:56:09","modified_gmt":"2024-01-28T02:56:09","slug":"dont-use-gaussians-in-stochastic-trace-estimation","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2024\/01\/28\/dont-use-gaussians-in-stochastic-trace-estimation\/","title":{"rendered":"Don’t Use Gaussians in Stochastic Trace Estimation"},"content":{"rendered":"\n

Suppose we are interested in estimating the trace<\/a> \"\tr(A) = \sum_{i=1}^n A_{ii}\" of an \"n\times n\" matrix \"A\" that can be only accessed through matrix\u2013vector products \"Ax_1,\ldots,Ax_m\". The classical method for this purpose is the Girard<\/a>\u2013Hutchinson<\/a> estimator

  <\/span>   <\/span>\"\[\hat{\tr} = \frac{1}{m} \left( x_1^\top Ax_1 + \cdots + x_m^\top Ax_m \right),\]\"<\/p>where the vectors \"x_1,\ldots,x_m\" are independent<\/a>, identically distributed<\/a> (iid) random vectors satisfying the isotropy condition <\/a>

  <\/span>   <\/span>\"\[\expect[x_ix_i^\top] = I.\]\"<\/p>Examples of vectors satisfying this condition include<\/p>\n\n\n\n