Title:  Lower bounds for the error decay incurred by coarse            
        quantization schemes in analog-to-digital conversion

Speaker:  Rachel Ward, NYU 

Abstract: 


Many real-word signals such as audio are naturally produced as real-valued bandlimited functions; that is, functions whose Fourier transform has compact support.  Because it is more efficient and robust to store and transmit signals in digital form, analog-to-digital conversion, or the study of accurate and stable methods for approximating such functions using a finite alphabet, is of great importance in modern signal processing.

According to the classical Shannon sampling theorem, bandlimited functions x(t) are completely determined (and easily reconstructed) from their values x(t_j) sampled at a rate greater than F (Hertz, say), where F is twice the maximal frequency of x.  This immediately gives a very natural analog-to-digital conversion scheme: acquire the signal values x(t_j), and replace each value by its M-bit truncated binary expansion.  As it turns out, the performance of this simple binary scheme is optimal, in the sense that the associated reconstruction error has optimal decay in terms of the number of bits used per critical sampling interval 1/F. 

However,  M-bit binary expansions are expensive to build in hardware (for large M); for this and other implementation issues, different quantization methods - specifically, coarse quantization methods - are more popular in practice.  In coarse quantization methods, as few as a single bit is allotted to represent each sample x(t_j), and better reconstruction accuracy is obtained by increasing the sampling rate. 

Until now, no lower bounds specific to coarse quantization schemes were known.  We provide the first such lower bound for the error decay rate.  In particular, we show that there is an explicit gap between the best possible performance of coarse quantization schemes, and the information-theoretic lower bound obtained by binary quantization.  That is, the advantages of coarse quantization come with the price of sub-optimal accuracy.  Our proof uses arguments from the theory of large deviations. 

This is joint work with Felix Krahmer, Hausdorff Center for Mathematics, Bonn, Germany.