We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
27/2009
Hierarchical Singular Value Decomposition of Tensors
Lars Grasedyck
Abstract
We define the hierarchical singular value decomposition (SVD) for tensors of order $d\ge2$. 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 (${\cal H}$-Tucker) which requires only ${\cal O}((d-1)k^3+dnk)$ data, where $d$ is the order of the tensor, $n$ the size of the modes and $k$ the rank. The ${\cal 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 ${\cal O}((d-1)k^4+dnk^2)$ and the attainable accuracy is just 2--3 digits less than machine precision.
