Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
55/2009

$O(d \log N)$-Quantics Approximation of $N$-$d$ Tensors in High-Dimensional Numerical Modeling

Boris N. Khoromskij

Abstract

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 \varepsilon^{-1})$-complexity bound for their approximation by low rank $2$-$(d \log N)$ quantics tensors up to the accuracy $\varepsilon >0$. In the case $\varepsilon = 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 \varepsilon^{-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.

Received:
Sep 7, 2009
Published:
Sep 7, 2009
MSC Codes:
65F30, 65F50, 65N35, 65F10
Keywords:
high-dimensional problems, quantics folding of vectors, rank structured tensor approximation, fem, matrix valued functions, material sciences, stochastic modeling

Related publications

inJournal
2011 Repository Open Access
Boris N. Khoromskij

\(O(d \log N) \)-quantics approximation of \(N\)-\(d\) tensors in high-dimensional numerical modeling

In: Constructive approximation, 34 (2011) 2, pp. 257-280