312	RWTH Publication No: 47276        2010        IGPM312.pdf
TITLE	Black Box Approximation of Tensors in Hierarchical Tucker Format
AUTHORS	Jonas Ballani, Lars Grasedyck, Melanie Kluge
ABSTRACT	We derive and analyse a scheme for the approximation of order d tensors A ∈ Rn×···×n in the hierarchical (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 H-Tucker format is O(dk3 + dnk) and we present a (heuristic) algorithm that finds an approximation to a tensor in the H-Tucker format in O(dk4 + d log(d)nk 2) by inspection of only dk + d log(d)nk2 entries. Under mild assumptions, tensors in the 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 ε automatically.
KEYWORDS	hierarchical Tucker, tensor rank, tensor approximation, tensor train, cross approximation
DOI	10.1016/j.laa.2011.08.010
PUBLICATION	Linear algebra and its applications 438(2), Seiten/Artikel-Nr.:639-657 (2011)