MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.