论文标题
对哈钦森的对角线估计器进行严格分析
A Tight Analysis of Hutchinson's Diagonal Estimator
论文作者
论文摘要
令$ \ mathbf {a} \ in \ mathbb {r}^{n \ times n} $是具有对角$ \ text {diag}（\ mathbf {a}）$的矩阵$，然后让$ \ bar {\ bar {\ mathbf {\ mathbf {a} a} $ $ \ tia its $ \ itsbf its assers assers assers assers assers n z}我们表明，Hutchinson的估计器以$ m $迭代的速度返回返回的对角线估计$ \ tilde {d} \ in \ Mathbb {r}^n $，以至于具有概率$（1-Δ）$，$ \ | \ | \ | \ tilde {d} {d} {d} - \ text {diag} - c \ sqrt {\ frac {\ log（2/δ）}} {m}}} \ | \ bar {\ mathbf {a}}} \ | _f，$ _f，$ c $，其中$ c $是固定常数独立于所有其他参数。这结果改善了[Baston和Nakatsukasa，2022]的最新结果，$ \ log（n）$ factor，产生了与矩阵尺寸$ n $无关的界限。
Let $\mathbf{A}\in \mathbb{R}^{n\times n}$ be a matrix with diagonal $\text{diag}(\mathbf{A})$ and let $\bar{\mathbf{A}}$ be $\mathbf{A}$ with its diagonal set to all zeros. We show that Hutchinson's estimator run for $m$ iterations returns a diagonal estimate $\tilde{d}\in \mathbb{R}^n$ such that with probability $(1-δ)$, $$\|\tilde{d} - \text{diag}(\mathbf{A})\|_2 \leq c\sqrt{\frac{\log(2/δ)}{m}}\|\bar{\mathbf{A}}\|_F,$$ where $c$ is a fixed constant independent of all other parameters. This results improves on a recent result of [Baston and Nakatsukasa, 2022] by a $\log(n)$ factor, yielding a bound that is independent of the matrix dimension $n$.
