Preprint 27/2009

Hierarchical Singular Value Decomposition of Tensors

Lars Grasedyck

Contact the author: Please use for correspondence this email.
Submission date: 26. Jun. 2009 (revised version: March 2010)
Pages: 29
published in: SIAM journal on matrix analysis and applications, 31 (2010) 4, p. 2029-2054 
DOI number (of the published article): 10.1137/090764189
Bibtex
Keywords and phrases: SVD, Tucker, Tensor
Download full preprint: PDF (331 kB)

Abstract:
We define the hierarchical singular value decomposition (SVD) for tensors of order formula7. 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 (formula11-Tucker) which requires only formula13 data, where d is the order of the tensor, n the size of the modes and k the rank. The formula11-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 formula27 and the attainable accuracy is just 2-3 digits less than machine precision.

03.07.2017, 01:41