Compressed Sensing

Module by: Siddharth Gupta, Grant Lee, Veena Padmanabhan, Heather Johnston

Summary: A brief introduction to compressed sensing and its advantages

Compressed sensing is based on exploiting sparsity. Sparse signals are those that can be represented as a combination of a small number of projections on a particular basis. (This new basis must be incoherent with the original basis.) Because of sparsity, the same signal can be represented with a smaller amount of data while still allowing for accurate reconstruction.

In non-compressed sensing methods, one would first aquire a large amount of data, compute an appropriate basis and projections on it, and then trasmit these projections and the basis used. This is wasteful of resources since many more data points are initially collected than are transmitted. In compressed sensing, a basis is chosen that will approximately represent any input sparse signal, as long as there is some allowable margin of error for reconstruction.

Figure 1: Comparison of different algorithms. Our project focuses on the third algorithm using random basis projections.

Comparison of Data Aquisition Algorithms that Use Sparsity

The pre-defined basis for the optimal case (as represented in the block diagram) can only be determined with prior knowledge of the signal to be aquired [1]. However, in practical applications such information is not usually known. To generalize to a basis that gives sparse projections for all images, a random basis can be used. A matrix of basis elements is generated from random numbers such that the basis elements are normal and orthogonal on average. Since using projections on a random basis is not the optimally sparse case, a larger number of projections must be taken to allow for reconstruction [2],[3]. However, this number is still far fewer than the number of datapoints taken using the traditional approach which exploits sparsity after data acquisition.

One application of compressed sensing is an N-pixel camera being designed by Takhar et al. which acquires much fewer than N data points to record an image [4].

For a more detailed explanation of compressed sensing, please refer to the literature on http://www.dsp.ece.rice.edu/cs

[1] D. Baron, M. B. Wakin, S. Sarvotham, M.F. Duarte and R. G. Baraniuk, “Distributed Compressed Sensing,” 2005, Preprint.

[2] E. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inform. Theory, 2004, Submitted.

[3] D. Donoho, “Compressed sensing,” 2004, Preprint.

[4] D. Takhar, V. Bansal, M. Wakin, M. Duarte, D. Baron, K. F. Kelly, and R. G. Baraniuk, “A compressed sensing camera: New theory and an implementation using digital micromirrors,” in Proc. Computational Imaging IV at SPIE Electronic Imaging, San Jose, January 2006, SPIE, To appear.

Comments, questions, feedback, criticisms?

Send feedback

• E-mail the authors of the module, Compressed Sensing

Footer

More about this content: Metadata | Version History

• How to reuse and attribute this content
• How to cite and attribute this content

This work is licensed by Siddharth Gupta, Grant Lee, Veena Padmanabhan, and Heather Johnston under a Creative Commons Attribution License (CC-BY 2.0).

Last edited by Heather Johnston on Dec 23, 2005 12:27 pm US/Central.