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

We consider a class of multilevel matrices, which arise from the discretization of linear diffusion operators in a $d$-dimensional hypercube. Under certain assumptions on the structure of the diffusion tensor (motivated by financial models), we derive an explicit representation of such a matrix in the recently introduced Tensor Train (TT) format with the $TT$ ranks bounded from above by $2 + \lfloor \frac{d}{2}\rfloor$. We also show that if the diffusion tensor is constant and semiseparable of order $r < \lfloor \frac{d}{2}\rfloor$, the representation can be refined and the bound on the TT ranks can be sharpened to $2 + r$ (we do this in a more general setting, for non-constant diffusion tensors of a certain structure). As a result, when $n$ degrees of freedom are used in each dimension, such a matrix is represented in the $TT$ format through $ O (d^3 n^2)$ and $ O(dn^2 r^2)$ parameters resp. instead of its $n^{2d}$ entries. We also discuss the representation of such a matrix in the Quantized Tensor Train $(QTT)$ decomposition in terms of $O(d^3 \log n)$ and $O(dr^2 \log n)$,parameters resp. Furthermore, we show that the assumption of semiseparability of order $r$ can be relaxed to that of quasi-separability of order $r$. We establish the direct relation $r_k = s_k +2$ between the $d -1$ $TT$ ranks $s_k$ of the matrix in question and the matrix ranks $r_k$ of the $d-1$ leading off-diagonal submatrices of the diffusion tensor