Tractability of the Approximation of High-Dimensional Rank One Tensors
Tractability of the Approximation of High-Dimensional Rank One Tensors
复制标题
DOI：
10.1007/s00365-015-9282-6
复制
发表时间：
2014-02
影响因子：
2.7
通讯作者：
E. Novak;Daniel Rudolf
中科院分区：
文献类型：
--
作者：
E. Novak;Daniel Rudolf
我们研究了高维秩一张量的近似使用点的评价，并考虑确定性以及随机算法。我们证明了对于某些参数（光滑性和阶导数的范数），这个问题是难处理的，而对于其他参数，这个问题是易处理的，并且对于每个固定的参数，其复杂性在维数上仅为多项式.对于随机算法，我们完全描述了一组参数，导致容易或困难的问题，分别。在“困难”的情况下，我们修改类以获得易处理的问题：如果函数的支持不是太小，则问题以多项式（在维度上）复杂度变得易处理。
We study the approximation of high-dimensional rank one tensors using point evaluations and consider deterministic as well as randomized algorithms. We prove that for certain parameters (smoothness and norm of theth derivative), this problem is intractable, while for other parameters, the problem is tractable and the complexity is only polynomial in the dimension for every fixed. For randomized algorithms, we completely characterize the set of parameters that lead to easy or difficult problems, respectively. In the “difficult” case, we modify the class to obtain a tractable problem: The problem gets tractable with a polynomial (in the dimension) complexity if the support of the function is not too small.