  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 storage costs that
partially explain the abundance of compressible tensors in applied mathematics.
For example, 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. As this bound is constructive, we are also able to solve this equation
spectrally with $\mathcal{O}(n (\log n)^3 (\log(1/\epsilon))^3)$ complexity.
