Numerical tensor-train ranks and tensor displacement structure

Tianyi Shi (CAM, Cornell University)

Tensors often have too many entries to be stored explicitly so it is essential to compress them into data sparse formats. I will identify three methodologies that can be used to explain when a tensor is compressible. Each methodology leads to bounds on the compressibility of certain tensors, partially explaining the abundance of low-rank tensors in applied mathematics. In particular, I will focus on tensors with a so-called displacement structure, showing that solutions to Poisson equations on tensor-product geometries are highly compressible. As the rank bounds are constructive, I will develop an optimal-complexity spectrally-accurate 3D Poisson solver with O(n(\log n)^2(log 1/epsilon)^2) complexity for a smooth righthand side, where nxnxn is the tensor discretization of the solution.