MiS Preprint Repository

In this article we introduce a black box type approximation algorithm for tensors $A$ in high dimension $d$. The algorithm determines adaptively the positions of entries of the tensor that have to be computed or read, and using these (few) entries it constructs a low rank tensor approximation $X$ that minimizes the ${\ell }_2$-distance between $A$ and $X$ at the chosen positions. The full tensor $A$ is not required, only the evaluation of $A$ at a few positions.

The minimization problem is solved by Newton's method which requires the computation and evaluation of the Hessian. For efficiency reasons the positions are located on fibre-crosses of the tensor so that the Hessian can be assembled and evaluated in a data-sparse form requiring a complexity of $\mathcal{O}(Pd)$, where $P$ is the number of fibre-crosses and $d$ the order of the tensor.