Frames from first principles: Error correction, symmetry goals, and numerical efficiency (09w5082)

Objectives

This workshop focuses on optimality principles in the digital encoding of analog signals, a topic which poses challenges for mathematics, electrical engineering and computer science.

Digital signal transmissions have revolutionized our daily lives, from cellular phones and Voice-over-Internet-Protocol telephony to High-Definition Television and other streaming media. The use of digitization helps suppress distortions typical for analog devices and allows seemingly faultless communication by incorporating redundancy, that is, repetetive information. However, at times the digital nature of error suppression leads to artifacts that do not resemble the graceful degradation we recall from analog technology. Such problems could range from blocky images, choppy satellite radio, or dropped cell-phone calls to possible instabilities in digital fly-by-wire control systems.

This undesirable behavior can be caused by imperfections in the digitization process or by transmissions using digital error-correction protocols which are not well-adapted to the type of analog signal under consideration. Understanding the best way to use redundancy in the digitization as well as in the transmission processes seems the key to significant progress in this field. In both cases, the quality of the reconstructed analog signal should be the guiding principle to the optimal design of systems for conversion and transmission. Engineers have already contributed many approaches to address this challenge, which give rise to interesting mathematical questions. Answering these questions as well as developing a systematic treatment is a primary motivation for this workshop.

The theory of frames is the mathematical formulation for incorporating redundancy in a linear representation of a signal. Oversampling of audio signals stored on Compact Discs is a simple example of such digital encoding. Recently, significant progress has been made to reduce the impact of typical errors in digital transmissions (round-off errors, noise and data loss) by the design of frames appropriate for signal encoding. However, these results have mostly addressed different sources of errors separately. For a more comprehensive treatment, the exchange of ideas between mathematics and engineering needs to be strengthened.

A frequent challenge in the design of frames is to meet a symmetry requirement. This could mean adapting the frame to resolve an image without directional preferences or encoding a cell phone signal in a way that makes it easy to adjust for delays or shifts in frequency due to motion of the handset. The detailed analysis of the group structure underlying such design constraints is essential for new results.

Numerical efficiency is often an important factor in the design of encoding. Recently, it has been shown that signals with sparse frame expansions can be recovered accurately by relatively few measurements. This is essential for ultra-wideband transmissions, where sampling at the Nyquist rate is unfeasible.
Apart from minimizing the number of required measurements, the computational effort of signal reconstruction is important for numerical efficiency. Hierarchical structures mimicking our cognitive system seem to offer a good trade-off between performance and computational effort. Wavelets, which are used for the encoding of images for High-Definition Television, incorporate such an efficient hierarchical structure, but their
redundancy-free design does not provide much flexibility to realize desirable symmetry properties, leading to commonly known block artifacts in images. Within the last few years, efficient image encoding techniques have been emerging, which avoid directional preferences with the help of frame representations.

Certain situations require a more refined notion of redundancy, for example, when sensors have been somewhat randomly scattered across a terrain or, in medical applications, a patient body. Assuming a fixed monitoring range for each sensor, they may overlap to varying degrees in different locations, which means they report with a varying amount of repetitive information. The flexible architecture of fusion frames offers a
general setting to explore optimal designs in this context. In fact, the underlying concept may be a more realistic model for our cognitive process, and allow us to realize its versatility in many applications of signal analysis and communication.

Generally, a comprehensive mathematical answer to the typical combination of problems treated by engineers requires a better understanding of both practical and theoretical aspects of frame design. This workshop aims at bringing together researchers from engineering and mathematics, in order to promote the exchange necessary for significant contributions to this field.

A preliminary draft of this proposal was circulated among 37 researchers (+5 organizers) to solicit for tentative participation in this proposed workshop. Within only two days, we received 27(+5) enthusiastic positive responses from internationally renowned mathematicians and engineers, including Richard Baraniuk (Rice), John Benedetto (Maryland), Robert Calderbank (Princeton), Hans Feichtinger (Vienna), Jelena Kovacevic (Carnegie Mellon), and David Larson (Texas A&M).