We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
60/2008
Black Box Low Tensor Rank Approximation using Fibre-Crosses
Mike Espig, Lars Grasedyck and Wolfgang Hackbusch
Abstract
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 ${\cal O}(Pd)$, where $P$ is the number of fibre-crosses and $d$ the order of the tensor.
