Hierarchical Singular Value Decomposition of Tensors

revised version: March 2010
Lars Grasedyck
(Please use for correspondence this email).

Submission date: 26. Jun. 2009
Pages: 29
published in: SIAM journal on matrix analysis and applications, 31 (2010) 4, p. 2029-2054 
DOI number (of the published article): http://dx.doi.org/10.1137/090764189
Keywords and phrases: SVD, Tucker, Tensor
Download preprint: PDF (331 kB)

Abstract:
We define the hierarchical singular value decomposition (SVD) for tensors of order . This hierarchical SVD has properties like the matrix SVD (and collapses to the SVD in d=2), and we prove these. In particular, one can find low rank (almost) best approximations in a hierarchical format (-Tucker) which requires only data, where d is the order of the tensor, n the size of the modes and k the rank. The -Tucker format is a specialization of the Tucker format and it contains as a special case all (canonical) rank k tensors. Based on this new concept of a hierarchical SVD we present algorithms for hierarchical tensor calculations allowing for a rigorous error analysis. The complexity of the truncation (finding lower rank approximations to hierarchical rank k tensors) is in and the attainable accuracy is just 2-3 digits less than machine precision.