308	RWTH Publication No: 47278        2010        IGPM308.pdf
TITLE	Polynomial Approximation in Hierarchical Tucker Format by Vector-Tensorization
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 point-wise 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