Optimal Encoding 1.1 2007/07/16 12:20:42.648 GMT-5 2007/09/21 22:59:29.190 GMT-5 Ronald A. DeVore devore@math.sc.edu Shriram Sarvotham shri@rice.edu Elchin Asgarov deoxman@gmail.com Raymond Wagner rwagner@rice.edu Richard G. Baraniuk richb@rice.edu Mark Davenport md@rice.edu Ronald A. DeVore devore@math.sc.edu Shriram Sarvotham shri@rice.edu We shall consider now the encoding of signals on [-T,T] where T>0 is fixed. Ultimately we shall be interested in encoding classes of bandlimited signals like the class B A However, we begin the story by considering the more general setting of encoding the elements of any given compact subset K of a normed linear space X. One can determine the best encoding of K by what is known as the Kolmogorov entropy of K in X. To begin, let us consider an encoder-decoder pair (E,D) E maps K to a finite stream of bits. D maps a stream of bits to a signal in X. This is illustrated in . Note that many functions can be mapped onto the same bitstream.

Illustration of encoding and decoding.

Define the distortion d for this encoder-decoder by d(K,E,D,X):=sup f∈K ∥f-D(Ef)∥ X ̲ ¯ . Let n(K,E)=sup f∈K #Ef where #Ef is the number of bits in the bitstream Ef. Thus n is the maximum length of the bitstreams for the various f∈K. There are two ways we can define optimal encoding: Prescribe ϵ, the maximum distortion that we are willing to tolerate. For this ϵ, find the smallest n ϵ (K,X):=inf (E,D) {n(K,E):d(K,E,D,X)≤ϵ}. This is the smallest bit budget under which we could encode all elements of K to distortion ϵ. Prescribe N : find the smallest distortion d(K,E,D,X) over all E,D with n(K,E)≤N. This is the best encoding performance possible with a prescribed bit budget. There is a simple mathematical solution to these two encoding problems based on the notion of Kolmogorov Entropy.