Abstract:For some kernel matrices, low-rank approximations can be quickly obtained via analytic techniques. One important class of analytic methods that has received attention in recent years is based on the use of proxy points. Accuracy analysis for various proxy point methods has often been heuristic in nature, other than for certain special kernels. For more general cases, the methods lack an explicit number or location of proxy points required to yield a particular approximation accuracy. In this work, we carry out new analysis of a proxy point method that is applicable to general complex-analytic kernels. An intuitive way of choosing proxy points is used to show explicit error bounds. Such bounds decay exponentially with regard to the number of proxy points. This also leads to convenient estimates of numerical ranks of relevant kernel matrices. To showcase the utility of this new analysis, we apply it to design a new sublinear-time hierarchically semiseparable approximation method for certain Toeplitz matrices, including ones that frequently arise from real-world applications. This allows, for example, inversion of such matrices with lower computational complexity compared with existing direct methods. Some extensions of these ideas are also discussed.
| Subjects: | Numerical Analysis (math.NA) |
| Cite as: | arXiv:2605.24231 [math.NA] |
| (or arXiv:2605.24231v1 [math.NA] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24231 arXiv-issued DOI via DataCite (pending registration) |
From: Mikhail Lepilov [view email]
[v1]
Fri, 22 May 2026 21:18:47 UTC (264 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。