On the numerical ranks of tensors

Tensors are often compressed by expressing them in low rank tensor formats. 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 numerical tensor ranks that partially explain the abundance of compressible tensors in applied mathematics. For example, we show that the solution tensor $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 $\epsilon$ by a tensor-train decomposition of rank $(1,s_1,s_2,1)$, where $s_1=s_2=\mathcal{O}(\log n \log(1/\epsilon))$ and $0 < \epsilon < 1$.