efficiently than is currently possible. The first chip for the project, which will sample frequencies at a rate of 800 million data points per second, is in fabrication now, and should soon be ready for testing. “One application for this kind of system,” says Romberg, “would be for monitoring large swaths of communications bandwidth, where you don’t necessarily know which frequency would be used for communicating.”

 

mathematical insights In addition to having an impact on the design of sensor systems and other industrial applications, compressed sensing is leading to new ways of looking at math problems in seemingly unrelated areas. Candes and Tao, for example, are currently working on the problem of matrix prediction, the most widely known example of which is the Netflix Prize. The goal of those working to win the prize is to improve the accuracy of the Netflix movie-recommendation system. Each Netflix customer watches and rates a small fraction of movies, so it is possible to know only a little of the matrix in advance. While other mathematical approaches, such as spectral graph theory, have been applied to such matrix-prediction problems, Candes and Tao say there are strong parallels to the kinds of problems that compressed sensing can address. “The point is that we believe the ratings matrix to be structured,” says Tao. “Emmanuel and I are not working directly on the Netflix Prize problem, but on some more founda-

compressed sensing
has applications for
biomedical imaging,
digital photography,
and other forms of
analog-to-digital
conversion.

tional mathematical issues related to one approach to solving this problem.”

As for the future of the theory, Romberg says that one challenge remaining for those working on compressed sensing is convincing people that there is some value in it, and a corresponding value in changing sensor systems that have been implemented in certain ways since the beginning of signal processing. “A lot of the theory of compressed sensing,” he says, “goes against everything that sensors have been designed to do.” Another challenge is developing more efficient reconstruction algorithms. Traditionally, the signal-processing workload happens during encoding (such as for music and image files), while the decoder does very little. In compressed sensing, the workload is reversed; the encoder does very little, but the decoder has to work to find the location of the signal, its amplitude,

news

and other characteristics. “A question that is active and that must remain active is how to get very fast algorithms to do the reconstruction,” says Candes.

For his part, Tao says compressed sensing is here to stay. “Perhaps in five or 10 years most of the issues people are actively studying now will be resolved or their limitations understood much better,” he says. “There is certainly a lot of potential, particularly in specific fields such as MRI, in which there was a definite need to squeeze more information out of fewer measurements.”

But compressed sensing’s impact, Tao says, is likely to be uneven, given that traditional methods might be more effective for some applications due to the limitations of compressed sensing that aren’t completely understood.

According to Candes, at least one impact of the theory is happening outside the research labs and on a more organic, social level. Candes says that when he attends conferences related to compressed sensing, he regularly sees pure mathematicians, applied mathematicians, computer scientists, and hardware engineers coming together to share ideas about the theory and its applications. “It’s really exciting to see all these people talk together,” Candes says. “I know compressed sensing is changing the way people think about data acquisition.”

based in los angeles, Kirk L. Kroeker is a freelance editor and writer specializing in science and technology.

© 2009 aCm 0001-0782/09/0500 $5.00

Obituary
Jacob T. Schwartz, 79, Dies

Jacob T. “Jack” schwartz, a mathematician and computer scientist who conducted important research in a wide variety of fields and founded the department of computer science at new york University, died on march 2. He was 79.

schwartz was well respected by his peers for his brilliance as a scientist, his skill and vision as a department chair, and a seemingly boundless intellectual curiosity. He first made a name for himself as a mathematics graduate student at yale when he co-authored, with his ph.d.

advisor nelson dunford, the three-volume Linear Operators. The text was first published in 1958 and, a half-century later, is still in print. (dunford and schwartz were jointly awarded the leroy p. steele prize from the american mathematical society for Linear Operators in 1981.)

among schwartz’s many achievements was pioneering work in optimizing compilers at IBm, with John Cocke and Frances e. allen, as a visiting scientist; the development of se Tl, an early programming language, and the Ultracomputer, one of the

first parallel computers; and the authorship of 18 books and more than 100 papers and reports.

schwartz was chair of the department of computer science at new york University’s Courant Institute of mathematical sciences from 1964 to 1980, which thrived during and after his term as chair. a fellow professor, edmond schonberg, recalls how “in the early 1980s, Jack attended a conference on robotics in Washington, d. C., and when he returned, he said, ‘This is a subject full of interesting scientific questions—and it is

eminently fundable.’ ” as a result, the department launched a large-scale robotics effort.

during his time at nyU, schwartz taught nearly every class offered by the department of computer science. “When Jack got interested in a subject, he would teach a course on it,” says schonberg. “as the course evolved, he would reinvent the subject for himself and define his own approach to it. and when he came to class, he would be ecstatic about having discovered something new, and this was contagious.”