MiS Preprint Repository

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high dimensional applications.

We describe the multi-folding or quantics based tensor approximation method of $O(d\log N)$-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set $\{1,...,N{\}}^{\otimes d}$, or briefly $N$-$d$ tensors of size $N^d$, and to the respective discretised differential-integral operators in ${\mathbb{R}}^d$. As the basic approximation result, we prove that complex exponential sampled on equispaced grid has quantics rank $1$. Moreover, the Chebyshev polynomial sampled over Chebyshev Gauss-Lobatto grid, has separation rank $2$ in quantics tensor format, while for the polynomial of degree $m$ the respective quantics rank is at most $m+1$.

For $N$-$d$ tensors generated by certain analytic functions, we give the constructive proof on the $O(d\log N\log {\epsilon }^{-1})$-complexity bound for their approximation by low rank $2$-$(d\log N)$ quantics tensors up to the accuracy $\epsilon >0$. In the case $\epsilon =O(N^{-\alpha })$, $\alpha >0$, our approach leads to the quantics tensor numerical method in dimension $d$, with the nearly optimal asymptotic complexity $O(d/\alpha {\log }^2{\epsilon }^{-1})$. >From numerics presented, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional FEM/BEM---the tool apparently works.