Kolmogorov entropy of a subset of $L^1$

Question

How can we estimate the Kolmogorov $\epsilon$-entropy $$H_\epsilon (A,L^1(\mathbb R))$$ where $ A = \{f:\mathbb R \to [0,K] \text{ s.t. $f \in L^1$ and has total variation $TV(f) \le M$}\} $?

Answer 1

$\newcommand\ep\epsilon \newcommand{\R}{\mathbb R} \newcommand{\de}{\delta}$For any positive real $K,M,\ep$, the $\ep$-entropy of your set $A$ is $\infty$.

Indeed, for any such $K,M,\ep$ and all natural $n$, let $f_n:=c\,1_{[0,3n\ep/c]}$, where $c:=\min(K,M/2)$. Then $f_n\in A$ for all $n$, and $\|f_n-f_m\|_1\ge3\ep$ for all distinct natural $n$ and $m$. So, $A$ has no finite $\ep$-net (because no $L^1$-ball of radius $\ep$ can contain two distinct functions among the infinitely many $f_n$'s).

---

As discussed in comments, the $\ep$-entropy of your set $A$ will be finite if we add the assumption that for some $g\in L^1(\R)$ and all $f\in A$ we have the domination $|f|\le g$.

Indeed, for each real $\de>0$ there is a real $b=b_\de>0$ such that \begin{equation*} \int_{\R\setminus[-b,b]}g\le\de. \tag{1}\label{eq:de} \end{equation*}

For each $f\in A$, the condition $TV(f)\le M$ implies a representation of the form \begin{equation*} f=c+f^+-f^- \tag{2}\label{eq:f=} \end{equation*} on the interval $[-b,b]$, where \begin{equation*} c:=f(-b)\in[0,K] \tag{3}\label{eq:c} \end{equation*} and $f^\pm$ are nondecreasing functions on $[-b,b]$ with $f^\pm(-b)=0$ and $f^\pm(b)\in[0,M]$.

For any natural $n$, all $i=0,\dots,n$, any $F\in\{f^+,f^-\}$, and any real $h>0$, let \begin{equation*} x_i:=-b+\frac{2b}n\,i,\quad y_i:=F(x_i),\quad j:=j_i:=\lceil y_i/h\rceil\big[\in[0,M/h+1]\big], \tag{3.5}\label{eq:x_i} \end{equation*} so that $x_0=-b$, $x_n=b$, and $y_i\le jh<y_i+h$. Hence, for each $i=0,\dots,n-1$ and all $x\in(x_i,x_{i+1})$ we have $F(x)-jh\le y_{i+1}-jh\le y_{i+1}-y_i$ and $jh-F(x)\le jh-y_i<h$, which implies $|F(x)-jh|\le y_{i+1}-y_i+h$, so that \begin{equation*} \int_{x_i}^{x_{i+1}}|F-jh|\le(y_{i+1}-y_i+h)\frac{2b}n. \end{equation*} Summing these inequalities in $i=0,\dots,n-1$, we get \begin{equation*} \int_{-b}^b|F-F_{n,h}|\le(F(b)-F(-b)+nh)\frac{2b}n\le(M+nh)\frac{2b}n, \tag{4}\label{eq:int_-b,b} \end{equation*} where $F_{n,h}:=j_ih$ on each of the intervals $(x_i,x_{i+1})$ for $i=0,\dots,n-1$, and $F_{n,h}:=0$ outside the union of these intervals.

Recall (\ref{eq:c}) and let \begin{equation*} k:=\lceil c/h\rceil\big[\in[0,K/h+1]\big], \tag{5}\label{eq:k} \end{equation*} so that $|c-kh|\le h$.

Recalling now (\ref{eq:f=}), (\ref{eq:int_-b,b}), condition $|f|\le g$, and (\ref{eq:de}), we get \begin{equation*} \int_{\R}|f-(kh+f^+_{n,h}-f^-_{n,h})\,1_{[-b,b]}|\le h+(M+nh)\frac{4b}n+\de. \end{equation*} In view of (\ref{eq:k}), there are $\le K/h+1$ constant functions of the form $kh$. In view of (\ref{eq:x_i}), there are $\le(2M/h+1)^n$ functions of the form $f^+_{n,h}-f^-_{n,h}$. So, assuming without loss of generality that $K\le2M$ and also assuming that \begin{equation*} h+(M+nh)\frac{4b_\de}n+\de\le\ep,\tag{6}\label{eq:<rp} \end{equation*} we have an $\ep$-net of $A$ consisting of \begin{equation*} N\le(K/h+2)(2M/h+3)^n\le(2M/h+3)^{n+1} \tag{7}\label{eq:N} \end{equation*} functions of the form $(kh+f^+_{n,h}-f^-_{n,h})\,1_{[-b_\ep,b_\ep]}$.

To be specific, we may now set $h=M/n$ and $\de=\ep/2$. Then conditions (\ref{eq:<rp}) and (\ref{eq:N}) become \begin{equation*} n\ge n_\ep:=\Big\lceil\frac{2(8b_{\ep/2}+1)M}\ep\Big\rceil \end{equation*} and \begin{equation*} N\le(2n+3)^{n+1}. \end{equation*} Thus, the $\ep$-entropy is \begin{equation*} \le(n_\ep+1)\log(2n_\ep+3). \end{equation*}