论文标题
用于估计真实对称矩阵的对角线的蒙特卡洛方法
Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix
论文作者
论文摘要
对于仅通过矩阵矢量产物才能访问的真实对称矩阵，我们提出了用于计算对角线元件的蒙特卡洛估计器。我们的概率绝对误差和相对误差的概率界限适用于基于随机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, 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 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. An application to derivative-based global sensitivity metrics corroborates 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.
