论文标题
对称不确定矩阵的随机低级别近似
Randomized low-rank approximation for symmetric indefinite matrices
论文作者
论文摘要
NyStröm方法是找到与对称阳性半明确基质的低级别近似值的流行选择。当应用于对称不确定矩阵时，该方法可能会失败，为此，误差可能无限。在这项工作中，我们首先确定找到与对称不确定矩阵的Nyström近似的主要挑战。然后，我们证明了一种克服不稳定性的变体的存在，并建立当奇异值迅速衰减时所产生的近似值的相对错误核标准界。该分析自然会导致一种实用算法，其鲁棒性通过实验说明。
The Nyström method is a popular choice for finding a low-rank approximation to a symmetric positive semi-definite matrix. The method can fail when applied to symmetric indefinite matrices, for which the error can be unboundedly large. In this work, we first identify the main challenges in finding a Nyström approximation to symmetric indefinite matrices. We then prove the existence of a variant that overcomes the instability, and establish relative-error nuclear norm bounds of the resulting approximation that hold when the singular values decay rapidly. The analysis naturally leads to a practical algorithm, whose robustness is illustrated with experiments.
