论文标题
无随机基质正交：随机兰斯佐斯正交和内核多项式方法的统一和统一边界
Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
论文作者
论文摘要
我们分析用于光谱和光谱总和近似的随机无基质正式层。所研究的算法包括核多项式方法和随机兰斯佐斯正交，这是这些任务的两种广泛使用的方法。我们对频谱近似的分析统一并简化了过去十年中出现的这些算法的几个一次性分析。此外，我们得出光谱总和的边界，以确保以高概率，算法在所有有界的分析函数上同时准确。最后，我们提供了全面和免费的数值示例。这些示例说明了算法之间的一些定性相似性和差异，以及它们在不同类型的问题上使用的相对缺点和好处。
We analyze randomized matrix-free quadrature algorithms for spectrum and spectral sum approximation. The algorithms studied include the kernel polynomial method and stochastic Lanczos quadrature, two widely used methods for these tasks. Our analysis of spectrum approximation unifies and simplifies several one-off analyses for these algorithms which have appeared over the past decade. In addition, we derive bounds for spectral sum approximation which guarantee that, with high probability, the algorithms are simultaneously accurate on all bounded analytic functions. Finally, we provide comprehensive and complimentary numerical examples. These examples illustrate some of the qualitative similarities and differences between the algorithms, as well as relative drawbacks and benefits to their use on different types of problems.
