论文标题
对称矩阵的随机关节对角线化
Randomized Joint Diagonalization of Symmetric Matrices
论文作者
论文摘要
鉴于一个几乎通勤的对称矩阵的家族，我们考虑了计算一个正交矩阵的任务，该矩阵几乎将家族中的每个矩阵对角线对角线。在本文中，我们建议和分析用于执行此任务的随机关节对角线化（RJD）。 RJD将标准特征值求解器应用于矩阵的随机线性组合。与现有的基于优化的方法不同，RJD易于实现，并利用现有的高质量线性代数软件包。我们的主要贡献是证明稳健的恢复：鉴于一个对通勤家庭的家庭为$ε$ - near，RJD共同对这个家庭进行对角线，并具有很高的可能性，最大可能是Norm o（$ε$）。我们还讨论了如何通过通缩技术进一步改进算法，并通过使用合成和现实世界数据的数值实验来证明其最先进的性能。
Given a family of nearly commuting symmetric matrices, we consider the task of computing an orthogonal matrix that nearly diagonalizes every matrix in the family. In this paper, we propose and analyze randomized joint diagonalization (RJD) for performing this task. RJD applies a standard eigenvalue solver to random linear combinations of the matrices. Unlike existing optimization-based methods, RJD is simple to implement and leverages existing high-quality linear algebra software packages. Our main novel contribution is to prove robust recovery: Given a family that is $ε$-near to a commuting family, RJD jointly diagonalizes this family, with high probability, up to an error of norm O($ε$). We also discuss how the algorithm can be further improved by deflation techniques and demonstrate its state-of-the-art performance by numerical experiments with synthetic and real-world data.
