2014/02/20 by Novak, Erich, Rudolf, Daniel
#41A25 #41A63 #65C05 #65D15 #65Y20 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1402.5011
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 the rth 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 ε>0. 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.