Search

MiS Preprint Repository

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.

Received:
Jun 26, 2009
Published:
Jun 29, 2009
Keywords:
SVD, Tucker, Tensor

Related publications

inJournal
2010 Repository Open Access
Lars Grasedyck

Hierarchical singular value decomposition of tensors

In: SIAM journal on matrix analysis and applications, 31 (2010) 4, pp. 2029-2054