Hierarchical Singular Value Decomposition of Tensors

We define the hierarchical singular value decomposition (SVD) for tensors of order d2. 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 (H-Tucker) which requires only O ( (d-1) k³+dnk) parameters, where d is the order of the tensor, n the size of the modes, and k the (hierarchical) rank. The H-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 O ( (d-1) k⁴+dnk²) and the attainable accuracy is just 2–3 digits less than machine precision.