compressed sensing

The compressed sensing problem is to design a set of linear measurements to recover a signal that is sparse or skewed. This problem has attracted huge interest across CS and EE since its formalization in 2004. It has been observed that sketch data structures including CM sketch are effective ways to solve compressed sensing problems, with a "decoding" stage that is much simpler and faster than methods based on LP-solving.

• • Experiments with CM-sketches for sparse approximation.

It has been observed that sketch data structures including CM sketch are effective ways to solve compressed sensing problems, with a "decoding" stage that is much simpler and faster than methods based on LP-solving.

• • Sparse Recovery Using Sparse Matrices. Anna Gilbert and Piotr Indyk. Proc of IEEE, 10.

Survey paper.

• Towards an Algorithmic Theory of Compressed Sensing. G. Cormode and S. Muthukrishnan, DIMACS Technical Report, 2005.

• Argues that sketch-like ideas can be applied to compressed sensing to obtain accurate reconstruction of arbitrary signals with high probability.