MiS Preprint Repository

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 ( 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

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