Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix
Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix
复制标题
估计实对称矩阵对角线的蒙特卡罗方法
DOI：
10.1137/22m1476277
复制
发表时间：
2023
影响因子：
1.5
通讯作者：
Saibaba, Arvind K.
中科院分区：
文献类型：
--
作者：
Hallman, Eric;Ipsen, Ilse C.;Saibaba, Arvind K.
对于只能通过矩阵向量积获得的实对称矩阵，我们给出了计算对角元的蒙特卡罗估计量。我们的标准绝对误差和相对误差的概率界适用于基于随机Rademacher、稀疏Rademacher和归一化和非归一化高斯向量的蒙特卡罗估计以及具有有界四次矩的向量。在我们的证明中，矩阵浓度不等的新颖使用代表了未来分析的系统模型。我们的界大多不明确地依赖于矩阵的维度，以不同于已有工作的误差度量为目标，并且意味着估计器的精度随着矩阵的对角优势而增加。网络科学中基于导数的全局灵敏度度量和节点中心性度量的应用证实了这一点，对合成测试矩阵的数值实验也证实了这一点。我们建议不要在实践中使用稀疏Rademacher向量，这是许多随机化草图和采样算法的基础，因为即使在大采样量下，它们往往也只能提供一位数的精度。
For real symmetric matrices that are accessible only through matrix vector products, we present Monte Carlo estimators for computing the diagonal elements. Our probabilistic bounds for normwise absolute and relative errors apply to Monte Carlo estimators based on random Rademacher, sparse Rademacher, and normalized and unnormalized Gaussian vectors and to vectors with bounded fourth moments. The novel use of matrix concentration inequalities in our proofs represents a systematic model for future analyses. Our bounds mostly do not depend explicitly on the matrix dimension, target different error measures than existing work, and imply that the accuracy of the estimators increases with the diagonal dominance of the matrix. Applications to derivative-based global sensitivity metrics and node centrality measures in network science corroborate this, as do numerical experiments on synthetic test matrices. We recommend against the use in practice of sparse Rademacher vectors, which are the basis for many randomized sketching and sampling algorithms, because they tend to deliver barely a digit of accuracy even under large sampling amounts.
登录
查看更多内容
DOI：
10.21220/s2cc7x
发表时间：
2016
期刊：
ArXiv
影响因子：
--
作者：
Jesse Laeuchli
通讯作者：
Jesse Laeuchli
DOI：
--
发表时间：
2022
期刊：
arXiv.org
影响因子：
--
作者：
R. Baston;Y. Nakatsukasa
通讯作者：
Y. Nakatsukasa
掩蔽样本协方差估计器：通过矩阵浓度不等式进行分析
DOI：
10.1093/imaiai/ias001
发表时间：
2011
期刊：
Information and Inference: A Journal of the IMA
影响因子：
--
作者：
Richard Y. Chen;Alex Gittens;J. Tropp
通讯作者：
J. Tropp
影响因子：
3.7
作者：
A. Soms
通讯作者：
A. Soms
DOI：
10.1007/978-3-319-97136-0_2
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Shashanka Ubaru;Y. Saad
通讯作者：
Y. Saad