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.