Search

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 (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
57/2010

Black Box Approximation of Tensors in Hierarchical Tucker Format

Jonas Ballani, Lars Grasedyck and Melanie Kluge

Abstract

We derive and analyse a scheme for the approximation of order $d$ tensors $A\in\mathbb{R}^{n\times\cdots\times n}$ in the hierarchical ($\cal H$-) Tucker format, a dimension-multilevel variant of the Tucker format and strongly related to the TT format. For a fixed rank parameter $k$, the storage complexity of a tensor in ${\cal H}$-Tucker format is ${\cal O}(dk^3+dnk)$ and we present a (heuristic) algorithm that finds an approximation to a tensor in the ${\cal H}$-Tucker format in ${\cal O}(dk^4+d\log(d)nk^2)$ by inspection of only ${\cal O}(dk^3+d\log(d)nk^2)$ entries. Under mild assumptions, tensors in the ${\cal H}$-Tucker format are reconstructed.

For general tensors we derive error bounds that are based on the approximability of matrices (matricizations of the tensor) by few outer products of its rows and columns. The construction parallelizes with respect to the order $d$ and we also propose an adaptive approach that aims at finding the rank parameter for a given target accuracy $\varepsilon$ automatically.

Received:
Oct 1, 2010
Published:
Oct 5, 2010
MSC Codes:
15A69, 65F99
Keywords:
Hierarchical Tucker, Tensor rank, tensor approximation, Tensor Train, Cross Approximation

Related publications

inJournal
2013 Repository Open Access
Jonas Ballani, Lars Grasedyck and Melanie Kluge

Black box approximation of tensors in hierarchical Tucker format

In: Linear algebra and its applications, 438 (2013) 2, pp. 639-657