In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies efficient representation of (compact) function classes $F$ defined on some compact set $G$ (continuous, smooth, analytic) by "tables". Let's say that we would like to approximate an element $f\in F$ up to accuracy $\epsilon$. A "table" can be thought of as a mapping $\Gamma:\omega^p \to N_{\epsilon}(F)$ where $N_{\epsilon}(F)$ is an $\epsilon$-net of $F$ and $\omega$ is a finite set of numbers (everything is considered in the uniform norm). The quantity $|\omega|^p$ is called the "table volume", and clearly it cannot be smaller than the minimal size of an $\epsilon$-net of $F$. Therefore $$p\log_2 |\omega| \geq H_{\epsilon}(F)\qquad (1)$$ where $H_{\epsilon}(F)=\log N_{\epsilon}(F)$ is the Kolmogorov's $\epsilon$-entropy.

Obviously, nothing more concrete can be said without restricting the nature of the reconstruction/approximation algorithms $\Gamma$. Vitushkin takes $$\Gamma = \{ P_x(\omega_1,\dots,\omega_p); \deg P\leq k \}$$ where $P$ is a poloynomial in $p$ variables of degree $k$ in each one, whose coefficients depend somehow on the coordinates $x\in G$. Then he shows that

  1. For subspaces $F$ of $d$-times continuously differentiable functions $$p\log(k+1)\geq H_{\epsilon}(F)$$
  2. For subspaces $F$ of analytic functions $$p\log({k+1\over \epsilon}) \geq H_{\epsilon}(F) \qquad (2)$$

Assume for the rest of the discussion that $k$ is fixed. Then the above suggests that "the complexity of representation" of analytic functions (the number of parameters $p$ in the table) can be made much smaller (by a factor of $\log {1\over \epsilon}$) than by using only considerations of metric entropy (compare $(2)$ with $(1)$).

Easily representable families

In proving $(2)$ Vitushkin uses the fact that the analytic functions are "easily representable", in the following sense.

Definition 1 For any finite subset $S=\{s_1,\dots,s_n\} \subset G$ of cardinality $n$, let $f(S)$ denote the set $$ f(S) = \{ \left(\Re f(s_1),\Re f(s_2),\dots,\Re f(s_n), \Im f(s_1),\Im f(s_2),\dots,\Im f(s_n) \right) : \; f\in F\} \subset \mathbf R^{2n}.$$

Definition 2: For given $\delta\geq \epsilon$, let $\nu_\epsilon^\delta(F)$ denote the minimal size of a subset $\alpha_\epsilon^\delta \subset G$ for which $$ H_\epsilon(f(\alpha_\epsilon^\delta)) \geq H_\delta(F).$$

Definition 3 A subspace $F$ is called "easily representable" if there exists a function $\delta=\delta(\epsilon)\geq 2\epsilon$, decreasing monotonically to zero as $\epsilon\to 0$, such that for any $B>0$ and for sufficiently small $\epsilon$ we have $\nu_{B\epsilon}^{\delta(\epsilon)} < +\infty$, and $$ \lim_{\epsilon\to 0} {\nu_{B\epsilon}^{\delta(\epsilon)} \over H_{\delta(\epsilon)}(F)}=0.$$

My question

Are there any known generalizations of the above ideas? For instance, the construction of the set $f(S)$ can be considered as a transformation of the space $F$ by the collection of linear functionals $$\{\delta_{s_1},\dots,\delta_{s_n} \} $$ (here $\delta$ is the delta-function).

Can one replace this collection by another set of linear functionals (i.e. changing Definition 1 to some other Definition 1'), and still get meaningful results, i.e. a non-empty set of "easily representable functions" in this new sense? What if one takes the first $n$ Fourier coefficients? (in this case one should also probably change the metric to $L^2$). Or even an arbitrary/random collection of $n$ linear functionals?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.