The Best Bits
A new technology called compressive sensing slims down data at the source
Spears and Nets
Can you expect to find a compressive-sensing device in your next digital camera or audio recorder? Probably not, but several research groups are actively exploring the prospects.
Kevin F. Kelly and his colleagues at Rice University have built a series of compressive-sensing cameras. At the heart of these devices is an array of micromirrors that can be independently switched between two positions. By swivelling the mirrors, light from any subset of pixels can be focused on a single photodetector, which thereby sums up the luminosity of the entire subset. The mirror array has an effective resolution of 65,536 pixels; the camera can produce images of equivalent resolution with a few thousand random-sample measurements.
For conventional photography, a mirror-array camera may never compete with the technology that puts 10 million photosensors on a single chip. But the compressive-sensing camera may find a niche elsewhere, such as imaging at wavelengths outside the visible range.
Another area where compressive sensing has promise is magnetic resonance imaging—where the whole story began. The imperative in MRI is not so much compressing data for storage but acquiring it quickly, because the patient must hold still while an image is formed. Ordinary after-the-fact compression is no help in this respect, but compressive sensing offers hope of faster scanning without loss of resolution or contrast.
Other likely areas of application are radio astronomy, where long-baseline interferometers operate at the limit of spatial resolution, and perhaps even genetic screening and analysis of gene activation, where hundreds or thousands of signals are difficult to extract from a noisy background.
Candès and Tao argue that compressive sensing is based on a kind of uncertainty principle, where the spectrum of the signal and that of the measuring instrument have complementary roles. The traditional sensing strategy takes sharply focused samples; it’s like hunting with a spear. This works well when the signal is spread out over a broad domain. But when the signal itself is highly structured and narrowly focused, the better plan is to spread the measurements out over the domain—to hunt with a net rather than a spear.
© Brian Hayes
- Baraniuk, Richard G., Emmanuel Candès, Robert Nowak and Martin Vetterli (editors). 2008. Special issue on compressive sampling. IEEE Signal Processing Magazine 25(2):12–13.
- Candès, Emmanuel J. 2006. Compressive sampling. In Proceedings of the International Congress of Mathematicians, Madrid, Spain, pp. 1433–1452.
- Candès, Emmanuel J., Justin Romberg and Terence Tao. 2006. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory 52:489–509.
- Candès, Emmanuel, and Justin Romberg. 2007. Sparsity and incoherence in compressive sampling. Inverse Problems 23:969–985.
- Candès, Emmanuel J., and Michael B. Wakin. 2008. An introduction to compressive sampling. IEEE Signal Processing Magazine 25(2):21–30.
- Donoho, David. 2006. Compressed sensing. IEEE Transactions on Information Theory 52:1289–1306.
- Lustig, Michael. 2008. Sparse MRI. Doctoral thesis, Stanford University. http://www-mrsrl.stanford.edu/~mlustig/thesis.pdf
- MacKenzie, Dana. 2009. Compressed sensing makes every pixel count. In What’s Happening in the Mathematical Sciences, Vol. 7. Providence, R.I.: American Mathematical Society.
- Romberg, Justin. 2008. Imaging via compressive sampling. IEEE Signal Processing Magazine 25(2)14–20.
- Takhar, Dharmpal, Jason N. Laska, Michael B. Wakin, Marco F. Duarte, Dror Baron, Shriram Sarvotham, Kevin F. Kelly and Richard G. Baraniuk. 2006. A new compressive imaging camera architecture using optical-domain compression. In Proceedings of the 2006 SPIE Conference on Computational Imaging, Vol. 6065.