Back to search

IS-AUR-Samarb.progr. Norge Frankrike

Recovering the Unseen: Coding Theory Applied to Compressed Sensing

Awarded: NOK 26,027

The reconstruction of a (mathematical) object from a partial set of observations in an efficient and reliable manner is of fundamental importance. Compressed sensing is a new research area in which the object to be reconstructed is a k-sparse signal vec tor (there are at most k nonzero entries in the vector) over the real numbers. The partial information provided is a linear transformation of the signal vector, the measurement vector, and the objective is to reconstruct the object from a small number of measurements. Much of the information we deal with on a daily basis is essentially sparse, or in other ways represented redundantly. This applies for example to images (that can be significantly compressed using e.g. JPEG) or audio (that can be compres sed by the use of e.g. MP3). The benefits of compressed sensing can be illustrated by a simple example of a digital image recorded by a digital camera. Such an image can usually be significantly compressed using standard JPEG compression, without any not iceable visual distortion, where the compression ratio depends on the actual image and the amount of noise allowed. Here, the data acquisition phase is massive, but most of the data is redundant and can be thrown away, since the image can be represented b y a k-sparse signal. This seems enormously wasteful, and the question is: Why can we not just measure the part that will not end up being thrown away? In this example, data acquisition is cheap although massive, and processing of raw data often takes plac e locally in the camera, but for other applications acquisition can be expensive (e.g. seismology) or intrusive (e.g. medical applications like MRI), or transmission of raw data can be costly (e.g. in wireless sensor networks, where power and bandwidth ar e limited resources). Compressed sensing can be used in this context to reduce the amount of raw data that needs to be acquired, and thus to make the whole process more efficient.

Funding scheme:

IS-AUR-Samarb.progr. Norge Frankrike