Low-rank tensor structure of linear diffusion operators in the TT and QTT formats

We consider a class of multilevel matrices arising, for example, from the discretization of linear diffusion operators in a d-dimensional hypercube. We derive explicit representations of such matrices in the Tensor Train (TT) format, introduced recently for the non-linear low-parametric approximation of multi-dimensional vectors with the aim to handle the “curse of dimensionality”. We obtain sharp upper bounds on the TT ranks, which are linear or, when the diffusion tensor is semiseparable or quasi-separable, even sublinear in d (cf. the straightforward quadratic estimate). The use of the Quantized Tensor Train (QTT) decomposition allows to further reduce the number of parameters.