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