Black box approximation of tensors in hierarchical Tucker format
type: Item
instance of: scholarly article
title: Black box approximation of tensors in hierarchical Tucker format
zbMATH Open document ID: 1260.65037
author: Jonas Ballani
author: Melanie Kluge
author: L. Grasedyck
published in: Linear Algebra and its Applications
publication date: 2013-01-16T00:00:00Z
review text: 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.
reviewed by: Rémi Vaillancourt
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A72
zbMATH DE Number: 6125881
zbMATH Keywords: hierarchical Tucker format
zbMATH Keywords: tensor rank
zbMATH Keywords: tensor approximation
zbMATH Keywords: tensor train
zbMATH Keywords: cross approximation
zbMATH Keywords: error bound
zbMATH Keywords: numerical examples
MaRDI profile type: Publication
full work available at URL: j.laa.2011.08.010
OpenAlex ID: W1967538125
cites work: A new scheme for the tensor representation
cites work: Hierarchical Singular Value Decomposition of Tensors
cites work: TT-cross approximation for multidimensional arrays
cites work: Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
cites work: Fast evaluation of singular BEM integrals based on tensor approximations
cites work: A Multilinear Singular Value Decomposition
cites work: An introduction to hierarchical (\(\mathcal H\)-) rank and TT-rank of tensors with examples
cites work: Tensor Decompositions and Applications
cites work: A theory of pseudoskeleton approximations
cites work: Approximation of boundary element matrices
cites work: Black box low tensor-rank approximation using fiber-crosses
cites work: Hybrid cross approximation of integral operators
DOI: 10.1016/J.LAA.2011.08.010
Recommended article: Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time
Recommended article: A Review on Adaptive Low-Rank Approximation Techniques in the Hierarchical Tensor Format
Recommended article: Linear algebra for tensor problems
Recommended article: Parallel Algorithms for Low Rank Tensor Arithmetic
Recommended article: Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats
Recommended article: Greedy low-rank approximation in Tucker format of solutions of tensor linear systems
Recommended article: On manifolds of tensors of fixed TT-rank
Recommended article: Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
Recommended article: Fast truncation of mode ranks for bilinear tensor operations
Recommended article: Two-level QTT-Tucker format for optimized tensor calculus
description: scientific article; zbMATH DE number 6125881