In Approximation Theory, the fundamental problem is to reconstruct a signalAinR^{n}from linear measurements <A,ψ_{i}> with respect to a dictionary Ψ forR^{n}. Recently, there has been tremendous excitement about the novel direction ofCompressed Sensing[?] where the reconstruction can be done with very few-O(klogn)-linear measurements over a modified dictionary Ψ' if the information of the signal is concentrated inkcoefficients over an orthonormal basis Ψ. 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

everysignal, faster algorithms for the reconstruction, as well as succinct transformations of Ψ to Ψ'.

*This file was generated by
bibtex2html 1.92.*