Stochastic diagonal estimation: probabilistic bounds and an improved algorithm
Stochastic diagonal estimation: probabilistic bounds and an improved algorithm
复制标题
随机对角线估计：概率界限和改进算法
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Y. Nakatsukasa
中科院分区：
文献类型：
--
作者：
R. Baston;Y. Nakatsukasa
本文研究了隐式给定矩阵A的对角线估计问题。对于这样一个矩阵，我们可以访问一个oracle，它允许我们计算矩阵向量积$Av$。对于从适当分布中提取的随机变量$v$，这可以用于返回矩阵$A$的对角线的估计值。虽然结果存在的概率保证有关的错误估计的跟踪$A$，没有这样的结果尚未得出对角线。我们分析的查询$s$的数量，以保证概率至少为$1-\delta$的对角条目的相对误差的估计是最多$\vareps $。我们将这种分析扩展到估计和$A$的对角线之间的差异的2范数。我们证明，讨论和实验的查询$s$的数量上的界限，以保证概率的对角线上的估计，采用Rademacher和高斯随机变量。证明了查询向量的最小数量的两个充分上界，扩展了Avron和Toledo的工作[JACM 58（2）8，2011]以及Roosta-Khorasani和Ascher的后期工作[FoCM 15，1187-1212，2015]。我们发现，一般来说，两者之间的差异很小，对于单个对角元素，收敛性为O（\log（1/\delta）/\varepsilon^2）$。然而，对于小的$s$，我们发现，Rademacher估计是上级。这些结果使我们能够扩展Meyer，Musco，Musco和Woodruff [SOSA，142-155，2021]的想法，建议算法Diag++，以加快对角估计的收敛速度从$O（1/\varepsilon^2）$到$O（1/\varepsilon^2）$，并使其对任何半正定矩阵$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-\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$.
DOI：
10.1137/1.9781611976496.16
发表时间：
2021-01
期刊：
Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA)
影响因子：
--
作者：
Meyer RA;Musco C;Musco C;Woodruff DP
通讯作者：
Woodruff DP