Entropy bounds for the absolute convex hull of tensors

Abstract

We derive entropy bounds for the absolute convex hull of vectors $X=(x_1,\dots ,x_p)\in {\mathbb{R}}^{n\times p}$ in ${\mathbb{R}}^n$ and apply this to the case where $X$ is the $d$-fold tensor matrix $$X=\underset{d\mathrm{times}}{\underbrace{\Psi \otimes \cdots \otimes \Psi }}\in {\mathbb{R}}^{m^d\times r^d},$$ with a given $\Psi =({\psi }_1,\dots ,{\psi }_r)\in {\mathbb{R}}^{m\times r}$, normalized to that $\Vert {\psi }_j{\Vert }_2\le 1$ for all $j\in \{1,\dots ,r\}$. For $\epsilon >0$ we let $\mathcal{V}\subset {\mathbb{R}}^m$ be the linear space with smallest dimension $M(\epsilon ,\Psi )$ such that ${\max }_{1\le j\le r}{\min }_{v\in \mathcal{V}}\Vert {\psi }_j-v{\Vert }_2\le \epsilon$. We call $M(\epsilon ,\psi )$ the $\epsilon$-approximation of $\Psi$ and assume it is -- up to log terms -- polynomial in $\epsilon$. We show that the entropy of the absolute convex hull of the $d$-fold tensor matrix $X$ is up to log-terms of the same order as the entropy for the case $d=1$. The results are generalized to absolute convex hulls of tensors of functions in $L_2(\mu )$ where $\mu$ is Lebesgue measure on $[0,1]$. As an application we consider the space of functions on $[0,1{]}^d$ with bounded $q$-th order Vitali total variation for a given $q\in \mathbb{N}$. As a by-product, we construct an orthonormal, piecewise polynomial, wavelet dictionary for functions that are well-approximated by piecewise polynomials.