## Compressed sensing review (0)

I plan to write an easy understanding review of compressed sensing, which is a popular topic that attracts considerable attention from 2004 and appears being related to more and more fields in recent years. The review will be posted in this blog as a series of notes about several aspects of compressed sensing:

1. Compressed sensing reconstruction algorithms ($\ell_1$ minimization, sparse signal recovery, reweighted/adaptive $\ell_1$);
2. Sparse coding (dictionary learning, K-SVD, MOD, MoTIF, FOCUSS);
3. Compressed sensing measurement (RIPs);
4. Why compressed sensing can exactly recover a sparse signal? (Incoherence, uncertainty principles)
5. Compressed sensing and statistics (feature selection, lasso, structure sparsity, covariance selection, group testing, permutation test)
6. Compressed sensing and learning (sparse dimension reduction, sparse PCA, data/label compression, model selection)

A brief history of compressed sensing:

The fundamental ideas of compressed sensing can be found from some literatures since  1960. David Dohono develops and completes the theories of compressed sensing in his early papers, e.g., UNCERTAINTY PRINCIPLES AND SIGNAL RECOVERY. Terence Tao and Emmanuel Candes construct the whole theoretical framework in several papers they published from 2005-2006, which can be found here. The rest, as they say, is history.

A brief introduction to compressed sensing:

For a sparse signal $x$, a few measurements (often linear and random, for example, $y=Ax$) much less than what Shannon-Nyquist sampling theorem determines are sufficient to exactly recover the signal $x$ by simple convex optimization.

Below is an illustration:

Illustration of compressed sensing