Analytical Low-Rank Compression via Proxy Point Selection
Analytical Low-Rank Compression via Proxy Point Selection
复制标题
DOI：
10.1137/19m1247838
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Xin Ye;J. Xia;Lexing Ying
中科院分区：
文献类型：
--
作者：
Xin Ye;J. Xia;Lexing Ying
势论中已知，对于一些与分离良好的点集相对应的核矩阵，可以通过使用代理点来实现快速分析低秩逼近。这种代理点方法提供了一种显式写出核矩阵的近似基矩阵的令人惊讶的方便方法。然而，这种优雅的策略在数值线性代数社区中很少为人所知或使用。它仍然需要对理论背景有清晰的代数理解。此外，仍然缺乏对近似误差的严格量化和选择代理点的可靠标准。在这项工作中，我们使用轮廓积分在一类重要的内核方面清楚地证明了这个想法。我们进一步为解析压缩提供全面的精度分析，并展示如何选择近乎最佳的代理点。然后，将分析压缩与快速的秩揭示分解相结合，以获得紧凑的低秩近似，并选择某些代表点。我们提供了所得总体低秩近似的误差界限。因此，这项工作提供了一种快速可靠的策略来压缩这些内核矩阵。此外，它提供了一种理解代理点方法的直观方法，并弥合了这种有用的分析策略和实际低秩近似之间的差距。一些数值例子有助于进一步说明这些想法。
It has been known in potential theory that, for some kernels matrices corresponding to well-separated point sets, fast analytical low-rank approximation can be achieved via the use of proxy points. This proxy point method gives a surprisingly convenient way of explicitly writing out approximate basis matrices for a kernel matrix. However, this elegant strategy is rarely known or used in the numerical linear algebra community. It still needs clear algebraic understanding of the theoretical background. Moreover, rigorous quantifications of the approximation errors and reliable criteria for the selection of the proxy points are still missing. In this work, we use contour integration to clearly justify the idea in terms of a class of important kernels. We further provide comprehensive accuracy analysis for the analytical compression and show how to choose nearly optimal proxy points. The analytical compression is then combined with fast rank-revealing factorizations to get compact low-rank approximations and also to select certain representative points. We provide the error bounds for the resulting overall low-rank approximation. This work thus gives a fast and reliable strategy for compressing those kernel matrices. Furthermore, it provides an intuitive way of understanding the proxy point method and bridges the gap between this useful analytical strategy and practical low-rank approximations. Some numerical examples help to further illustrate the ideas.