The Hackbusch conjecture on tensor formats

Weronika Buczynska*, Jaroslaw Buczynski, Mateusz Michalek

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We prove a conjecture of W. Hackbusch about tensor network states related to a perfect binary tree and train track tree. Tensor network states are used to present seemingly complicated tensors in a relatively simple and efficient manner. Each such presentation is described by a binary tree and a collection of vector spaces, one for each vertex of the tree. A problem suggested by Wolfgang Hackbusch and Joseph Landsberg is to compare the complexities of encodings, if one presents the same tensor with respect to two different trees. We answer this question when the two trees are extremal cases: the most "spread" tree (perfect binary tree), and the "deepest" binary tree (train track tree). The corresponding tensor formats are called hierarchical formats (HF) and tensor train (TT) formats, respectively. (C) 2015 Elsevier Masson SAS. All rights reserved.

Original languageEnglish
Pages (from-to)749-761
Number of pages13
JournalJOURNAL DE MATHEMATIQUES PURES ET APPLIQUEES
Volume104
Issue number4
DOIs
Publication statusPublished - Oct 2015
MoE publication typeA1 Journal article-refereed

Keywords

  • Hackbusch conjecture
  • Tensor formats
  • Hierarchical format
  • TT formats
  • Complexity of tensors
  • DECOMPOSITION

Cite this