Coarsely Quantized Redundant Representations of Signals (06w5078)

Objectives

This workshop intends to bring together expert mathematicians and theoretical engineers working on problems related or relevant to signal representations in coarsely grained environments. The workshop will highlight the links to other mathematical disciplines, such as combinatorics, dynamical systems and harmonic analysis.

Coarse quantization is emerging as a part of a larger technological trend towards robust and redundant systems which utilize low cost components. For quantization, the fundamental trade-off is between redundancy and cheap hardware, e.g., 1-bit quantizers. Daubechies and Calderbank (both of whom expressed a desire to attend this workshop) introduced the paradigm of "democracy of bits" to discuss this in a general setting. This trend is further illustrated by the recent parallel advances in the sensors community, where dense microsensor networks using large numbers of highly correlated, but inexpensive, sensors are currently a huge area of focus. It is no coincidence that much of today's cutting edge technology, such as Super Audio CD (SACD) systems, contains coarse quantization as a key component.

From an application point of view, the main focus of the workshop will be sigma-delta modulation in analog-to-digital encoding and error diffusion in digital halftoning:

Sigma-delta modulation is an oversampled analog-to-digital (A/D) conversion method for audio signals. A typical approach in obtaining digital representations of audio signals is to take the binary expansion of signal samples taken at the critical Nyquist rate of 44.1 KHz. However, this method suffers from high accuracy demands on the analog circuitry that is to be employed. Sigma-delta modulation, on the other hand, allocates as few as 1 bit for the discretization of signal samples taken at rates as high as 100 times faster than the critical rate. At the heart of this method lies an algorithm that recursively rounds (quantizes) each sample value to one of the few quantization levels in a way that is suited to achieve small global reconstruction error rather than small individual sample error.

The analogous problem in two dimensions is the problem of digital halftoning of images. While today's printers can achieve high resolution in space (such as 1200 dpi), most often only single tone dots are available to be printed on the corresponding medium. In this case, only 0's and 1's can be used to represent efficiently any shade of the gray-scale. Error diffusion can be thought of the exact analog of sigma-delta modulation in two dimensional signals and achieves this conversion effectively.

Sigma-delta modulation has its roots in the 60's when Inose and Yasuda developed the first unity bit encoding by negative feedback. Similarly, the classical error diffusion algorithm of Floyd and Steinberg was invented in the 70's. In the late 80's, interest in the information theory community was led by Gray who discovered some of the best known theoretical results. It was, however, only in the late 90's that an approximation theoretical framework was given to the problem by Daubechies and DeVore. Since then, there has been a rapid development in the theoretical analysis of sigma-delta modulation with emerging connections to other mathematical fields.

The problem of one-bit quantization is related to many other mathematical disciplines. Some of these would be regarded as classical now, but at the same time many connections are new or relatively unexplored.

- Combinatorics: combinatorial, geometric and linear discrepancy theory form the common grounds for understanding some of the fundamental problems in one-bit quantization, especially in understanding some of the universal lower bounds.

- Dynamical systems: most algorithms that yield efficient one-bit or low-bit representations are based on dynamical systems (sigma-delta modulation and error diffusion both fall into this category). Typically, underlying these dynamical systems are certain non-expanding piecewise affine maps on the Euclidean space. There is a strong connection between understanding the stability properties of these maps in high dimensions and the asymptotic performance of the associated algorithms.

- Functional and harmonic analysis: a natural analytical framework to study oversampled coarse quantization lies within the theory of frames. While the quantization problem in an orthonormal basis is trivial, there is no corresponding theory for redundant representations. Progress in this direction can also have far reaching consequences in compression and denoising.

It is important to note that one of the objectives of the workshop is to bring together mathematicians and engineers who are otherwise less likely to interact due to the distances in their respective fields of expertise. In particular, new links to combinatorics and frame theory are emerging, and we believe that holding this proposal during the suggested time-frame will make a significant impact. It should be stressed that better mathematical understanding holds great promise for better design paradigms. In addition, it is also intended to create a forum in which practical issues lead to theoretical problems and possibly abstract results find applications.