Wave Amplitude
Wave Amplitude
Time Time
the left image represents high-frequency radar pulses. in the right image, the original signal (blue) is overlapped by the reconstructed signal (red), which was built through compressed sensing at a rate that is 6% of what is required by the Shannon-nyquist theory.
sistance. Candes and his Caltech team set out to reconstruct the MRI images without any artifacts and by using only 5% of the sampled imaging data.
“When I looked at the artifacts, I discovered that they had certain features that I knew I could make go away by penalizing them in the reconstruction,” says Candes, who notes he was simply hoping his algorithm would improve the quality of the images. “That’s where the surprise came in,” he says. “What I was not expecting was that it would give me the truth.” Candes says that he and his team quickly realized they could do something that nobody thought was possible: simultaneous acquisition and compression. “That was the birth of compressed sensing,” he says. “We found that you can reconstruct images from dramatically fewer samples than what was previously necessary.”
Justin Romberg, who worked with Candes on the initial MRI project, points out that finding sparse signals that satisfy a set of linear constraints was an idea “floating around in the literature” at the time. However, he says, no existing theories supported the notion that it would be possible to perform reconstruction from limited data. “We were the first people to talk about it in this way,” says Romberg, a professor of electrical and computer engineering at the Georgia Institute of Technology. Of course, compressed sensing does not make it possible to reconstruct anything and everything from limited information. The target image or data set must have some special structure. “If there is structure, you can actually do much better than the Shannon-Nyquist theorem dictates,” says Romberg. “You can sample more efficiently.”
There are many projects in research
labs around the world to build hardware that can leverage some of the core ideas associated with compressed sensing, so one might assume that the theory has come of age. But given the requirement to know some structure of the expected signal prior to sampling—implying that a random signal or one consisting entirely of noise would not be well suited to compressed sensing—the research team sought to establish firm mathematical foundations for their results. “For the theory, we know a lot today, not all that we would like to know,” says Candes. “But in broad strokes, the foundation is there.”
theoretical applications One of the people who helped establish this foundation is Terence Tao, a professor of mathematics at the University of California, Los Angeles. “Emmanuel had found a toy problem in pure mathematics which, if solved, could lead to a practical demonstration that compressed sensing could actually work effectively,” says Tao. “That problem was in two areas in my own expertise—Fourier analysis and random matrices—and so I started to play around with it.” Eventually, says
Tao, he, Candes, and Romberg solved that toy problem, establishing that compressed sensing worked for a certain type of measurement related to the Fourier transform, and started working together to further develop the theory. “I would not say that the field is anywhere as mature as, say, Shannon’s theory of information, or the statistical theory of least squares regression, which are some of the precursors to this subject,” says Tao. “But the core ideas of the subject are by now quite well understood, even if there are still many areas where we would like to develop them further.”
One of the areas that needs more attention, according to Tao, is how the theory is centered around linear measurement. “We don’t yet know what to do if our measurement devices behave nonlinearly with respect to the data,” Tao says. “We are still exploring exactly what type of measurement models compressed sensing excels at, and where the paradigm reaches its limits and must be replaced or supplemented by a different type of method.”
Compressed sensing works for a large number of special-purpose situations, says Tao, but is probably not suitable as a general-purpose tool. For instance, he says, it is unlikely that general-purpose digital cameras will rely on compressed sensing, given that consumers might want to take pictures that look like random, unstructured images. “But a dedicated sensor network that is devoted to detecting a certain special type of signal might benefit substantially from this paradigm,” he says.
Indeed, compressed sensing is having an impact on the designs of a broad array of such applications, given that sensors can be found almost everywhere. Engineers at Rice University, for example, are working on a single-pixel camera that can take high-quality photos by using compressed sensing and a digital micromirror array. In addition, space agencies have shown interest in the theory, with initial designs outlined for cameras that rely on compressed sensing to save power in deep space. And Candes and Romberg are working on a project with DARPA to overcome some of the traditional limitations associated with the analog-to-digital conversion of radio signals. The project’s goal is to design a system for monitoring radio frequency bands much more
References:
Archives