论文标题
随机对角线估计：概率界限和改进的算法
Stochastic diagonal estimation: probabilistic bounds and an improved algorithm
论文作者
论文摘要
我们研究了估计一个隐式给定矩阵$ a $的对角线的问题。对于这样的矩阵，我们可以访问甲骨文，该甲板使我们能够评估矩阵矢量product $ av $。对于从适当分布中得出的随机变量$ v $，这可用于返回矩阵$ a $的对角线的估计。概率保证存在与$ a $ $ a $的估计误差有关的概率保证的结果，但尚未为对角线得出这样的结果。我们分析了确保概率至少$ 1-δ$所需的查询$ S $数量，对角条目的相对误差的估计最多为$ \ varepsilon $。我们将此分析扩展到$ a $的估计和对角线之间的差异的2个norm。我们通过使用Rademacher和Gaussian随机变量来证明，讨论和尝试有关确保对角线估计的概率限制所需的查询$ S $数量的界限。证明了最小的查询向量数量的两个足够的上限，从而扩展了Avron和Toledo的工作[JACM 58（2）8，2011]，后来又扩展了Roosta-Khorasani和Ascher的工作[FOCM 15，1187-1187-1212，2015]。我们发现，通常两者之间几乎没有区别，而收敛为$ o（\ log（1/δ）/\ varepsilon^2）$用于单个对角线元素。但是，对于小$ S $，我们发现Rademacher估计器是优越的。 These results allow us to then extend the ideas of Meyer, Musco, Musco and Woodruff [SOSA, 142-155, 2021], suggesting algorithm Diag++, to speed up the convergence of diagonal estimation from $O(1/\varepsilon^2)$ to $O(1/\varepsilon)$ and make it robust to the spectrum of any positive semi-definite矩阵$ a $。
We study the problem of estimating the diagonal of an implicitly given matrix $A$. For such a matrix we have access to an oracle that allows us to evaluate the matrix vector product $Av$. For random variable $v$ drawn from an appropriate distribution, this may be used to return an estimate of the diagonal of the matrix $A$. Whilst results exist for probabilistic guarantees relating to the error of estimates of the trace of $A$, no such results have yet been derived for the diagonal. We analyse the number of queries $s$ required to guarantee that with probability at least $1-δ$ the estimates of the relative error of the diagonal entries is at most $\varepsilon$. We extend this analysis to the 2-norm of the difference between the estimate and the diagonal of $A$. We prove, discuss and experiment with bounds on the number of queries $s$ required to guarantee a probabilistic bound on the estimates of the diagonal by employing Rademacher and Gaussian random variables. Two sufficient upper bounds on the minimum number of query vectors are proved, extending the work of Avron and Toledo [JACM 58(2)8, 2011], and later work of Roosta-Khorasani and Ascher [FoCM 15, 1187-1212, 2015]. We find that, generally, there is little difference between the two, with convergence going as $O(\log(1/δ)/\varepsilon^2)$ for individual diagonal elements. However for small $s$, we find that the Rademacher estimator is superior. These results allow us to then extend the ideas of Meyer, Musco, Musco and Woodruff [SOSA, 142-155, 2021], suggesting algorithm Diag++, to speed up the convergence of diagonal estimation from $O(1/\varepsilon^2)$ to $O(1/\varepsilon)$ and make it robust to the spectrum of any positive semi-definite matrix $A$.
