Title: Efficient Decomposition of High-Rank Tensors,
Abstract: Tensors are a natural way to express correlations among many physical
variables, but storing tensors in a computer naively requires memory which
scales exponentially in the rank of the tensor. This is not optimal, as the
required memory is actually set not by the rank but by the mutual information
amongst the variables in question. Representations such as the tensor tree
perform near-optimally when the tree decomposition is chosen to reflect the
correlation structure in question, but making such a choice is non-trivial and
good heuristics remain highly context-specific. In this work I present two new
algorithms for choosing efficient tree decompositions, independent of the
physical context of the tensor. The first is a brute-force algorithm which
produces optimal decompositions up to truncation error but is generally
impractical for high-rank tensors, as the number of possible choices grows
exponentially in rank. The second is a greedy algorithm, and while it is not
optimal it performs extremely well in numerical experiments while having
runtime which makes it practical even for tensors of very high rank.