Recovery algorithms for high-dimensional rank one tensors

We present deterministic algorithms for the uniform recovery of d-variate rank one tensors from function values. These tensors are given as product of d univariate functions whose rth weak derivative is bounded by M. The recovery problem is known to suffer from the curse of dimensionality for M≥2rr!. For smaller M, a randomized algorithm is known which breaks the curse. We construct a deterministic algorithm which is even less costly. In fact, we completely characterize the tractability of this problem by distinguishing three different ranges of the parameter M.