On the Compressibility of Tensors
Tianyi Shi, Alex Townsend
Abstract
Tensors are often compressed by expressing them in data-sparse tensor formats, where storage costs in such formats are less than those in the original structure. In this paper, we develop three methodologies that bound the compressibility of a tensor: (1) Algebraic structure, (2) smoothness, and (3) displacement structure. For each methodology, we derive bounds on storage costs in various low rank tensor formats that partially explain the abundance of compressible tensors in applied mathematics. For example, using displacement structure, we show that the solution tensor $\mathcal{X} \in \mathbb{C}^{n \times n \times n}$ of a discretized Poisson equation $-\nabla^2 u =1$ on $[-1,1]^3$ with zero Dirichlet conditions can be approximated to a relative accuracy of $0<\epsilon<1$ in the Frobenius norm by a tensor in tensor-train format with $\mathcal{O}(n (\log n)^2 (\log(1/\epsilon))^2)$ degrees of freedom. The constructive bound also allows us to design a spectral algorithm that solves this equation with $\mathcal{O}(n (\log n)^3 (\log(1/\epsilon))^3)$ complexity.