Deanna Needell & Joel A. Tropp Discuss Compressed Sensing

Fast Breaking Commentary, August 2010

Deanna Needell

Article: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

Authors: Needell, D;Tropp, JA
Volume: 26
Issue: 3
Page: 301-321
Year: MAY 2009
* Univ Calif Davis, Dept Math, 1 Shields Ave, Davis, CA 95616 USA.
* Univ Calif Davis, Dept Math, Davis, CA 95616 USA.
* CALTECH, Pasadena, CA 91125 USA.

Deanna Needell & Joel A. Tropp talk with and answer a few questions about this month's Fast Breaking Paper paper in the field of Mathematics.

SW: Why do you think your paper is highly cited?

Our paper is in the fast growing field of compressed sensing (CS) which addresses the problem of recovering a compressible signal from few noisy measurements (see description below).

We describe the first algorithm that provides all the benefits of previous approaches, and it tends to work better than other simpler algorithms, especially with regard to noise. Not only do we provide a method which is optimal in every important aspect, but we give a set of tools that allows people to analyze other algorithms and shows that they are also successful.

SW: Does it describe a new discovery, methodology, or synthesis of knowledge?

Yes, we use a standard framework but present a new synthesis of tools used previously. We combine these tools in a novel way to develop and analyze the algorithm. The algorithm is largely based on other approaches, but the novelty lies in how we use these ideas to construct a new method which is essentially optimal.

SW: Would you summarize the significance of your paper in layman's terms?

Joel A. Tropp
Coauthor Joel A. Tropp

CS is a relatively new field that originated because of an unfavorable opinion about signal compression methodology, which acquires the entire signal only then to throw away most of the information during compression.

The question was thus raised whether the acquisition and compression could be done simultaneously, sensing the signal directly using few linear measurements. The answer to this question turns out to be yes, and so the key problem in compressed sensing is to reconstruct the signal from these few linear measurements.

Of course this is an ill-posed problem in general, but under the assumption that the signal is compressible (contains far less information than its ambient dimension suggests), recovery is possible. Many signals of interest (such as images) are compressible and thus the applications of compressed sensing are widespread.

There are two major approaches to this problem, each having their own advantages and shortcomings. The first approach is convex optimization, which provides strong recovery guarantees but may be computationally challenging.

The second is the greedy approach, which provides very fast algorithms but weaker recovery guarantees. Our greedy algorithm provides the benefits of both: fast runtime as a greedy algorithm and also strong guarantees analogous to those of convex optimization.

SW: How did you become involved in this research, and how would you describe the particular challenges, setbacks, and successes that you've encountered along the way?

We became involved in CS because our work naturally led us to this area. CS benefits from a variety of different disciplines and the research has very many practical applications.

Along with the success of this work and others, there of course have been challenges as well. Typical challenges in this type of research which we have also encountered include the extension from sparse signals to compressible signals, removing parasitic logarithmic factors in error bounds, and refining results to be completely optimal at every aspect.

SW: Where do you see your research leading in the future?

This work provides a method to reconstruct signals, and much research is being done to extend these types of ideas to matrices.

Problems like matrix completion and low rank approximations are receiving much attention now, and are an exciting direction of research.

SW: Do you foresee any social or political implications for your research?

The recovery problem which our algorithm addresses has many practical applications. These applications range from medical imaging and coding theory to astronomy and geophysics. The research in this field can be used to improve devices and methods in these areas and also improves the understanding of the information theoretic limits and how far they can be pushed. The implications may turn out to be quite astounding.End

Deanna Needell
Postdoctoral Fellow in Statistics Department
Stanford University
Palo Alto, CA, USA

Joel A. Tropp
Assistant Professor of Applied & Computational Mathematics
California Institute of Technology
Pasadena, CA, USA


Citing URL:


   |   BACK TO TOP