{"id":2310,"date":"2026-03-03T02:58:28","date_gmt":"2026-03-03T02:58:28","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=2310"},"modified":"2026-03-03T02:59:33","modified_gmt":"2026-03-03T02:59:33","slug":"note-to-self-trace-estimation-with-tensor-products","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2026\/03\/03\/note-to-self-trace-estimation-with-tensor-products\/","title":{"rendered":"Note to Self: Trace Estimation with Tensor Products"},"content":{"rendered":"\n

Let \"x_1,\ldots,x_\ell\" be random vectors and let \"x = x_1 \otimes \cdots \otimes x_\ell\" denote their tensor product<\/a>. Assume the vectors \"x_i\" are isotropic<\/a>, in the sense that

  <\/span>   <\/span>\"\[\expect[x_i^{\vphantom{\top}} x_i^\top] = I.\]\"<\/p>The vector \"x\" inherits the isotropy property as well \"\expect[xx^\top] = I\". As a consequence, we can use the vector \"x\" to form an unbiased<\/a> estimator for the matrix trace<\/a> \"\expect[x^\top Ax] = \tr(A)\". Trace estimation has been a frequent topic on<\/a> this<\/a> blog<\/a>.<\/p>\n\n\n\n

What is the variance of the trace estimate \"x^\top Ax\"? This question was addressed<\/a> by Raphael Meyer<\/a> and Haim Avron<\/a>. The variance<\/a> of the trace estimator \"x^\top A x\" is

  <\/span>   <\/span>\"\[\Var(x^\top A x) = \expect[(x^\top A x)^2] - \expect[x^\top A x]^2 = \expect[(x^\top A x)^2] - \tr(A)^2.\]\"<\/p>As such, bounding the variance is equivalent to bounding the second moment \"\expect[(x^\top A x)^2]\". Suppose that the individual base vectors \"x_i\" satisfy a moment bound

(1) <\/span>   <\/span>\"\[\expect[(x_i^\top A x_i)^2] \le \alpha \tr(A)^2 \quad \text{for every psd matrix } A.\]\"<\/p>For instance, Gaussian, random sign, and uniformly random vectors on the sphere all satisfy<\/a> this bound with \"\alpha \le 3\". Under assumption (1), Meyer and Avron show that the tensor-product trace estimator \"x^\top Ax\" satisfies the bound

(2) <\/span>   <\/span>\"\[\expect[(x^\top A x)^2] \le \alpha^\ell \tr(A)^2 \quad \text{for any psd matrix } A.\]\"<\/p>Here, a matrix \"A\" is positive semidefinite<\/a> (psd) if it is symmetric<\/a> and satisfies \"v^\top A v \ge 0\" for any vector \"v\". Observe, the constant in the bound (2) is exponentially larger than the constant in bound (1). Unfortunately, as Meyer and Avron show<\/a>, this exponentially large variance is a real property of the tensor-structured trace estimator, at least on worst-case examples.<\/p>\n\n\n\n

Meyer and Avron’s paper<\/a> is really nice, and it contains many different results for Kronecker-structured trace estimation beyond the bound (2). I highly recommend checking their paper<\/a> out, which was just appeared<\/a> in the SIAM Journal of Matrix Analysis and Applications<\/a><\/em>! In this blog, I’ll give an alternate, somewhat shorter proof of the Meyer\u2013Avron bound (2).<\/p>\n\n\n\n

Suppose that \"x = y \otimes z\" is a tensor product of isotropic vectors \"y\in \real^{d_1}\" and \"z \in \real^{n_2}\", and suppose that

(3) <\/span>   <\/span>\"\[\expect[(y^\top A_1 y)^2] \le \alpha_1 \tr(A_1)^2 \quad \text{and} \quad \expect[(z^\top A_2 z)^2] \le \alpha_2 \tr(A_2)^2 \]\"<\/p>for any psd matrices \"A_1\" and \"A_2\". Now, let \"A\" be an \"(d_1n_2)\times(d_1n_2)\" psd matrix, and partition<\/a> \"A\" as

(4) <\/span>   <\/span>\"\[A = \begin{bmatrix} A_{11} & \cdots & A_{1d_1} \\ \vdots & \ddots & \vdots \\ A_{d_1 1} & \cdots & A_{d_1 d_1} \end{bmatrix}. \]\"<\/p>Then

(1) <\/span>   <\/span>\"\begin{align*}x^\top A x &= \begin{bmatrix} y_1 z \\ \vdots \\ y_{d_1}z\end{bmatrix}^\top\begin{bmatrix} A_{11} & \cdots & A_{1d_1} \\ \vdots & \ddots & \vdots \\ A_{d_1 1} & \cdots & A_{d_1 d_1} \end{bmatrix}\begin{bmatrix} y_1 z \\ \vdots \\ y_{d_1}z\end{bmatrix} \\ &= \underbrace{\begin{bmatrix} y_1 \\ \vdots \\ y_{d_1}\end{bmatrix}^\top}_{y^\top}\begin{bmatrix} z^\top A_{11}z & \cdots & z^\top A_{1d_1}z \\ \vdots & \ddots & \vdots \\ z^\top A_{d_1 1}z & \cdots & z^\top A_{d_1 d_1}z \end{bmatrix}\underbrace{\begin{bmatrix} y_1 \\ \vdots \\ y_{d_1}\end{bmatrix}}_y.\end{align*}\"<\/p>Taking the expectation over the random vector \"y\" alone<\/a> and applying (3), we obtain

(2) <\/span>   <\/span>\"\begin{align*}\expect_y [(x^\top A x)^2] &\le \alpha_1 \left( \tr \begin{bmatrix} z^\top A_{11}z & \cdots & z^\top A_{1d_1}z \\ \vdots & \ddots & \vdots \\ z^\top A_{d_1 1}z & \cdots & z^\top A_{d_1 d_1}z \end{bmatrix} \right)^2 \\ &= \alpha_1 [z^\top(A_{11}+\cdots+ A_{d_1d_1})z]^2.\end{align*}\"<\/p>Taking the expectation over \"z\" and invoking the law of total expectation<\/a> then yields

(3) <\/span>   <\/span>\"\begin{align*}\expect [(x^\top A x)^2] &\le \alpha_1 \alpha_2 \tr(A_{11}+\cdots+ A_{d_1d_1})^2=\alpha_1 \alpha_2\tr(A)^2.\end{align*}\"<\/p>In the last line, we observe that the trace of \"A\" is the sum of the traces of its diagonal blocks \"A_{ii}\". Voil\u00e0! We have deduced the bound

  <\/span>   <\/span>\"\[\expect [(x^\top A x)^2] \le \alpha_1\alpha_2 \tr(A)^2,\]\"<\/p>which immediately yields the Meyer\u2013Avron bound (2) by iteration.<\/p>\n","protected":false},"excerpt":{"rendered":"

Let be random vectors and let denote their tensor product. Assume the vectors are isotropic, in the sense that     The vector inherits the isotropy property as well . As a consequence, we can use the vector to form an unbiased estimator for the matrix trace . Trace estimation has been a frequent topicRead more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,14],"tags":[],"class_list":["post-2310","post","type-post","status-publish","format-standard","hentry","category-note-to-self","category-trace-estimation"],"_links":{"self":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/comments?post=2310"}],"version-history":[{"count":10,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2310\/revisions"}],"predecessor-version":[{"id":2321,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/posts\/2310\/revisions\/2321"}],"wp:attachment":[{"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/media?parent=2310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/categories?post=2310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ethanepperly.com\/index.php\/wp-json\/wp\/v2\/tags?post=2310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}