MiS Preprint Repository

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

Black Box Low Tensor Rank Approximation using Fibre-Crosses

Mike Espig, Lars Grasedyck and Wolfgang Hackbusch


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.

Sep 24, 2008
Sep 24, 2008
MSC Codes:
15A69, 90C06, 65K10
Low Rank, Tensor, Newton, Cross Approximation, Fibre-Crosses, Black Box

Related publications

2009 Journal Open Access
Mike Espig, Lars Grasedyck and Wolfgang Hackbusch

Black box low tensor-rank approximation using fiber-crosses

In: Constructive approximation, 30 (2009) 3, pp. 557-597