2.1 New signal models

We now wish to consider new model classes for signals. Towards this end, let ${\{{\psi }_j\}}_{j=1}^{\infty }$ be an orthonormal basis for $L_2(-T,T)$ . Thus for $f\in L_2$ we can write $f={\sum }_{j=1}^{\infty }{c}_j(f){\psi }_j$ where $(c_j(f))\in {\ell }_2$ . We will now build an encoder and decoder and analyze its performance oncompact sets $K$ . For example, we might want to encode signals in the space with norm $$\parallel f\parallel {}_{X_p}:=\parallel \left(c{}_j\right(f\left)\right)\parallel {}_{{\mathrm{\ell }}_p}.$$ However, in this space the unit ball, $U(X_p)$ is not compact. To get a compact set we need more structure on the sequence $(c_j)$ . Hence we define and we define the norm in this space as $\parallel f{\parallel }_{Y^{\alpha }}^{}:=$ the smallest $c$ such that this holds. We now take $$K=U(X_p)\cap U(Y^{\alpha })$$ to get a compact set. Notice that when $\alpha >0$ is small the requirement for membership in $Y^{\alpha }$ is very mild.

Next, suppose that we choose a target distortion level $\epsilon =2^{-m}$ . Given $f$ , let for , where $M:=\lceil \frac{2m}{2-p}\rceil$ . We then choose $N$ as the smallest integer so that $$N^{-\alpha }\le 2^{-M}$$ and thus $$\log N\le Cm\text{.}$$ It follows from the requirement that $f\in Y^{\alpha }$ that ${\Lambda }_k\subset \{1,\dots ,N\}$ for each .

Recall that $$\#{\mathrm{\Lambda }}_k{\mathrm{\hspace{0.25em}2}}^{\left(-k-1\right)p}\le \sum _{c_j\in {\mathrm{\Lambda }}_k}{\left|c_j\right|}^p\le {\parallel f\parallel }_{X_p}^p.$$ Since $f\in U(X_p)\cap U(Y^{\alpha })$ , $$\#{\mathrm{\Lambda }}_k\le {\parallel f\parallel }_{{\mathrm{\ell }}_p}{2}^{\left(k+1\right)p}\le 2^{\left(k+1\right)p}.$$ Hence, the total number of indices in all of the ${\Lambda }_k$ , , is $O(2^{Mp})$ .

To encode, for each $f$ , we can send the following bits:

• Send $\log n$ bits to identify each index in ${\Lambda }_k$ , for . This will require a total of $O(\log N{2}^{Mp})$ bits.
• Send one bit to identify the sign of $c_j(f)$ for each $j\in {\Lambda }_k$ , . This will require $O(2^{Mp})$ bits.
• Send $m$ bits to describe each $c_j(f),j\in {\Lambda }_k$ , for . This will require $O(m{2}^{Mp})$ bits.

Notice that for each $j\in {\Lambda }_k$ , , we can recover each $c_j(f)$ by $$\overline{c_j}=\pm \sum _{i=0}^m{b}_i{2}^{-k-i}$$ where the sign is given by the sign bit. It follows that for every such coefficient. Here we have used the fact that knowing that $j\in {\Lambda }_k$ means that the first nonzero binary bit of $c_j(f)$ is the $k$ -th bit.

To decode we simply set $$\overline{f}=\sum _{k=0}^M\sum _{j\in {\Lambda }_k}\overline{c_j}{\psi }_j$$

We now analyze the error we have incurred in such an encoding. The square of the error will consist of two parts. The first corresponds to the $j\in {\Lambda }_k$ , . For each such $j$ we have and so the total square error for this is $$\le C\sum _{k=1}^M{2}^{kp}{2}^{-2m}{2}^{-2k}\le c{2}^{-2m}$$ because . The second part of the error corresponds to all the coefficients which have magnitude $\le 2^{-M}$ . We have that this sum does not exceed Thus the total error we incur is $O(2^{-m})$ .

In summary, by allocating $O(m{2}^{\frac{m}{1∕p-1∕2}})$ bits we achieve distortion $C{2}^{-m}$ . Equivalently, by allocating $n\log n$ bits, we achieve distortion $C{n}^{-(1∕p-1∕2)}$ .

This is within a logarithmic factor of the optimal encoding given by Kolmogorov entropy of the class $U(X_p)\cap Y^{\alpha }$ . A slightly more careful argument can remove this logarithm.