Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

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