Deanna Needell & Joel A. Tropp Discuss Compressed Sensing
Fast Breaking Commentary, August 2010
|
Article: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Authors: Needell, D;Tropp, JA |
Deanna Needell & Joel A. Tropp talk with ScienceWatch.com and answer a few questions about this month's Fast Breaking Paper paper in the field of Mathematics.
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.
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.
Would you summarize the significance of your paper
in layman's terms?
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.
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.
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.
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.
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
KEYWORDS: COSAMP, SIGNAL RECOVERY, ALGORITHMS, APPROXIMATION, BASIS PURSUIT, COMPRESSED SENSING, ORTHOGONAL MATCHING PURSUIT, RESTRICTED ISOMETRY PROPERTY, SPARSE APPROXIMATION, UNCERTAINTY PRINCIPLE.