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


About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in notes and tagged , , . Bookmark the permalink.

2 Responses to Compressed sensing review (0)

  1. Euro says:

    Nice graph~~

  2. idmsj says:

    that’s a great start!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s