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-\delta$ 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/\delta)/\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$.
翻译:我们研究的是估算一个隐含给定的基质$A$的对角值问题。 对于这样一个基质, 我们能够访问一个能让我们评估矩阵矢量产品$Av$的星座。 对于从适当分布中抽取的随机变量$V$, 这可用于返回对基质对角值的估算值 $A美元。 虽然对12美元估算值的误差存在概率保障, 但仍没有得出这种结果 。 对于这个基质的强度, 我们分析需要多少查询值来保证至少1美元对基质值的对角值。 我们分析的是, 通过使用 Rademacher 和 高调来保证对基质值的估算值至少为1美元对德尔塔$。 对于顶层条目中相对错误的估算值最高为$avaleqoria $A$A$。 我们将这一分析扩大到2个基质的估算值, 美元对2015年基质的对基质值到基质值的对基质值的测算值的对数值做出小的估算值。 使用Rademacher 和基亚氏的数值 。