Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions
Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions
复制标题
DOI：
10.1007/s10444-022-09979-7
复制
发表时间：
2021-07
影响因子：
1.7
通讯作者：
A. Saibaba;R. Minster;M. Kilmer
中科院分区：
文献类型：
--
作者：
A. Saibaba;R. Minster;M. Kilmer
在本文中，我们介绍了一种多元函数逼近的方法，使用函数评估，切比雪夫多项式，和基于张量的压缩技术通过塔克格式。我们开发了新的随机技术来完成张量压缩，提供了一个详细的分析计算成本，提供洞察所得近似的错误，并讨论所提出的方法的好处。我们还应用基于张量的函数近似来开发低秩矩阵近似，以描述两组点之间的成对相互作用的核矩阵;由此产生的低秩近似计算和存储效率高（复杂度在点数上是线性的）。我们提出了一个自适应版本的函数和内核近似，确定一个近似，满足用户指定的相对误差超过一组随机点。我们扩展我们的方法的情况下，内核需要重复评估的许多值（超）参数，管理内核。我们给出了详细的数值实验的例子问题，涉及多元函数近似，低秩矩阵近似的核矩阵，涉及良好分离的集群的源和目标点，和一个全球性的低秩近似的核矩阵与高斯过程的应用。我们观察到的加速比标准的基于矩阵的方法高达18倍。
In this paper, we introduce a method for multivariate function approximation using function evaluations, Chebyshev polynomials, and tensor-based compression techniques via the Tucker format. We develop novel randomized techniques to accomplish the tensor compression, provide a detailed analysis of the computational costs, provide insight into the error of the resulting approximations, and discuss the benefits of the proposed approaches. We also apply the tensor-based function approximation to develop low-rank matrix approximations to kernel matrices that describe pairwise interactions between two sets of points; the resulting low-rank approximations are efficient to compute and store (the complexity is linear in the number of points). We present an adaptive version of the function and kernel approximation that determines an approximation that satisfies a user-specified relative error over a set of random points. We extend our approach to the case where the kernel requires repeated evaluations for many values of (hyper)parameters that govern the kernel. We give detailed numerical experiments on example problems involving multivariate function approximation, low-rank matrix approximations of kernel matrices involving well-separated clusters of sources and target points, and a global low-rank approximation of kernel matrices with an application to Gaussian processes. We observe speedups up to 18X over standard matrix-based approaches.