|
Could you summarize the
significance of your paper in layman’s terms?
Central to science is the task of
finding the most parsimonious description of a phenomenon or dataset.
However, there are often enormous numbers of descriptions which are
equally accurate. Finding the simplest one from among these would seem
to be intractable.
|
“Our paper introduced some simple notions that many scientists and engineers could understand, and showed that with such simple notions, surprising results could be proved easily and also observed computationally.”
|
|
This paper studied a simple setting in which this conundrum arises
and obtained a surprising result showing that the problem was not at
all hopeless.
It considered a signal processing problem where one has n
values of a signal which might be a superposition of some terms from
among 2n possible elementary signals (e.g., sinusoids,
wavelets). A description of the signal would be a way of superposing
the 2n elementary signals to reproduce the n observed data.
Here there are 2n unknowns, coefficients showing how strongly
each elementary signal is to participate, but only n data. In
the language of college algebra, we have more unknowns than equations.
The "simplest" description would use as few terms from
among the 2n as possible. It seems that this can only be found
by massive search, trying all possible subsets of elementary signals
to find the smallest one that works. If this were so, the simplest
description would be a useless concept, never applicable in practice.
The paper introduced the notion of "incoherence" of the
set of elementary signals—this is a useful concept when
orthogonality cannot hold. The paper showed that, for incoherent
systems, one might be able to find the simplest solution by minimizing
the sum of absolute values of the coefficients. Luckily, minimizing
the sum of absolute values of coefficients, subject to linear
constraints, is a standard problem of linear programming, and so is
very tractable. This problem is often called l1-norm minimization, and
the concept introduced in the paper was that solving underdetermined
systems of equations y=Ax where there are n equations and 2n unknowns,
finding the solution x with minimal l1 norm would often yield the
sparsest solution – the one with fewest nonzeros.
As a result, an important problem is seen in some cases not to be
intractable. Many other researchers picked up the hints from this
paper and found many situations where the simplest solution is
available by l1-norm minimization. Other researchers found still
simpler algorithms can even be used in particular cases. Implications
range across many areas of scientific measurement, signal processing,
and imaging.
Why do you think your paper is highly cited?
Our paper introduced some simple notions that many
scientists and engineers could understand, and showed that
with such simple notions, surprising results could be proved
easily and also observed computationally. This made it
attractive to many readers.
Since then, several researchers solved many much more
challenging versions of this type of problem, using more
difficult concepts and techniques, while in the process
citing our work.
It also turned out that the general problem—finding
sparse solutions to underdetermined systems of equations—is
of very broad significance in science and technology, with
applications ranging from statistical modeling to medical
imaging, to proteomics to wireless communications.
Thus other researchers could use the general approach of
minimizing the l1 norm subject to linear equality and/or
inequality constraints in many different applications areas,
often citing this paper as they did so.
Finally, the problem of minimizing the sum of absolute
values of the coefficients subject to linear constraints is
an attractive computational problem. Several researchers
worked to speed up and simplify it and also cited this work
in the process.
Does it describe a new discovery, methodology, or
synthesis of knowledge?
The paper was partly a synthesis of ideas—introducing a
viewpoint about underdetermined systems of linear equations,
about incoherent linear systems, and about minimum
L1 norm solutions—in an appealing package. The
paper also marks the discovery that this simple package
actually allows sharply-stated and striking conclusions, and
that computer experiments show the situation to be even
better than the theory was able to prove at the time.
How did you become involved in this research, and were
any problems encountered along the way?
Xiaoming Huo’s thesis concerned the use of more than n
elementary signals to represent signals for which we
observe n values. His empirical results were
surprisingly good. The paper was an attempt to give a
rigorous discussion showing that the empirical results were
correct and sensible.
Are there any social or political implications for your
research?
Emmanuel Candès at the California Institute of
Technology and Michael Lustig at Stanford University have
shown that magnetic resonance imaging (MRI) can be
dramatically sped up using ideas related to this paper. Such
applications may even save lives.
Jean-Luc Starck of the Service d'Astrophysique CEA/Saclay,
France and Michael Elad of the Computer Science Department
of the Technion—Israel Institute of Technology have shown
that various image processing tasks can be attacked anew
with ideas traceable to this paper. Improved image
processing may be useful in science and in our increasingly
technological society.
David L. Donoho
Anne T. and Robert M. Bass Professor
Statistics Department, Stanford University
Stanford, CA, USA
Xiaoming Huo
Associate Professor
School of ISyE, Georgia Institute of Technology
Atlanta, GA, USA
Read
an interview from in-cites.com in the Scientist category with David
L. Donoho.
|
Return to menu of Emerging Research Fronts
