308

IGPM308.pdf April 2010 
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 