308

RWTH Publication No: 47278 2010 IGPM308.pdf 
TITLE 
Polynomial Approximation in Hierarchical Tucker Format by VectorTensorization 
AUTHORS 
Lars Grasedyck 
ABSTRACT 
We analyze and characterize the possibility to represent or approximate tensors that stem from a tensorization of vectors, matrices, or tensors by low (hierarchical) rank. Our main result is that for vectors that stem from the evaluation of a polynomial f of degree p on an equispaced grid, the (hierarchical) rank is bounded by 1 + p. This is not true for the canonical rank, and we prove this by a small counterexample. We extend our result to functions with (few) singularities that are otherwise analytic: for an asymptotically smooth function with m singularities the rank required to achieve a pointwise accuracy of ε is of the size k ≤ C + log2 (1/ε) + 2m. The storage requirements for a tensorized vector of length n are O(log(n)k3 ) and arithmetic operations (e.g., truncated addition) in the format are of O(log(n)k4) complexity. 
KEYWORDS 
hierarchical Tucker, tensorization, tensor rank, tensor approximation, tensor train, TT 