with respect to a
dictionary Psi for R^n. Recently, there has been tremendous excitement
about the novel direction of Compressed Sensing [Donoho 04] where the
reconstruction can be done with very few---O(k log n)---linear
measurements over a modified dictionary Psi' if the information of the
signal is concentrated in k coefficients over an orthonormal basis Psi.
These results have reconstruction error on any given signal that is
optimal with respect to a broad class of signals. In a series of papers
and meetings over the past year, a theory of Compressed Sensing has been
developed by mathematicians.
We develop an algorithmic perspective for the Compressed Sensing problem,
showing that Compressed Sensing results resonate with prior work in Group
Testing, Learning theory and Streaming algorithms. Our main contributions
are new algorithms that present the most general results for Compressed
Sensing with (1+eps) approximation on every signal, faster algorithms for
the reconstruction, as well as succinct transformations of Psi to Psi'.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-25.pdf
DIMACS Home Page