Black box approximation of tensors in hierarchical Tucker format (Q1931758)

The authors heuristically reconstruct tensors that can be represented exactly in the \(\mathcal{H}\)-Tucker format with representation ranks \((k_t)_{t\in T_I}\), by inspection of only \(\mathcal{O}(dk^3+d \log(d)nk^2)\) entries (\(k := \max_{t\in T_I} k_t , n := \max_{\mu\in D} n_\mu)\) in complexity \(\mathcal{O}(dk^4 + d \log(d)nk^2)\). A similar result is obtained by \textit{I. Oseledets} and \textit{E. Tyrtyshnikov} [Linear Algebra Appl. 432, No. 1, 70--88 (2010; Zbl 1183.65040)] for the TT format. The difference is not only that the authors' construction applies for the \(\mathcal{H}\)-Tucker format, but also that the pivot elements as well as their number are chosen adaptively and incremental to achieve a prescribed accuracy \(\epsilon\) in the \(\|\cdot\|_\infty\)-norm. One can therefore estimate the error of the remainder during the construction, determine the necessary ranks and update an already computed approximation if a higher accuracy is required. Under rather strong assumptions, an error bound is derived for the approximation in the case that the tensor has a higher (possibly full) representation rank. In the numerical examples it is observed that the error in the \(\|\cdot\|_\infty\)-norm is typically close to the prescribed stopping tolerance \(\epsilon\), that is, in practice there is almost no error amplification. It is notable that even for random tensors the numerical results show a stable and almost optimal approximation.