

Preprint 55/2009
O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling
Boris N. Khoromskij
Contact the author: Please use for correspondence this email.
Submission date: 07. Sep. 2009 (revised version: August 2010)
Pages: 23
published in: Constructive approximation, 34 (2011) 2, p. 257-280
DOI number (of the published article): 10.1007/s00365-011-9131-1
Bibtex
MSC-Numbers: 65F30, 65F50, 65N35, 65F10
Keywords and phrases: high-dimensional problems, quantics folding of vectors, rank structured tensor approximation, fem, matrix valued functions, material sciences, stochastic modeling
Download full preprint: PDF (289 kB)
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 -complexity (logarithmic scaling in the volume
size), applied to the discrete functions over the product index set
, or briefly N-d tensors of size
,
and to the respective discretised differential-integral operators
in
. 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
-complexity bound for their
approximation by low rank 2-
quantics tensors
up to the accuracy
.
In the case
,
, our approach leads to
the quantics tensor numerical method in dimension d, with
the nearly optimal asymptotic complexity
.
>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.