The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTrace and XNysTrace, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard-Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs.
翻译:隐含的跟踪估计问题要求通过矩阵矢量产品(矩阵矢量产品)获取的方格矩阵的近似值。 本文设计了新的随机算法、 XTrace 和 XNysTrace, 以便通过利用差异减少和可交换性原则解决跟踪估算问题。 对于固定的配方计算预算, 数字实验显示, 新方法可以产生比现有算法( 如Girard- Hutchinson 估量器 或 Hutch++ 估量器) 规模小于现有算法( 如 Girard- Hutchinson 估量器 ) 的差错。 理论分析通过精确描述这些算法作为输入矩阵频谱函数的功能的性能来证实这些算法的效益。 文件还开发了一个可交换的估量器 XDiag, 用于使用矩阵对正方矩阵的对角矩阵进行对角。