Recovery algorithms for high-dimensional rank one tensors
For researchers in high-dimensional approximation, this work provides a complete tractability characterization and a more efficient deterministic algorithm for a problem previously only solvable by randomized methods.
The paper addresses the uniform recovery of high-dimensional rank one tensors from function values, where each univariate component has bounded weak derivatives. It presents a deterministic algorithm that breaks the curse of dimensionality for certain parameter ranges, achieving lower cost than previous randomized methods, and fully characterizes tractability across three regimes of the smoothness parameter M.
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 $r$th weak derivative is bounded by $M$. The recovery problem is known to suffer from the curse of dimensionality for $M\geq 2^r r!$. 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 three different ranges of the parameter $M$.