Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.
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.
