## G. Cormode and S. Muthukrishnan.
Towards an algorithmic theory of compressed sensing.
Technical Report 2005-25, Center for Discrete Mathematics and
Computer Science (DIMACS), 2005.

In Approximation Theory, the fundamental problem is to reconstruct a
signal A in R^n from linear measurements 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+ε) approximation on every signal, faster algorithms for
the reconstruction, as well as succinct transformations of Psi to Psi'.

[ bib |
Alternate Version |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*