Compressed Sensing

This summer I am on my third work term in TO in this company called IFDS. I have been assigned a task like always to research on this term called compressed sensing, brainstorm this idea and implement it in the real world. But what is COMPRESSED SENSING, this idea has made me believe that once implemented it can lead to a new technology while clicking images and saving them.
The main idea behind compressed sensing is to exploit that there is some structure and redundancy in the majority of interesting signals—they are not pure noise. In particular, most signals are sparse, that is, they contain many coefficients close to or equal to zero, when represented in some domain. (This is the same insight used in many forms of lossy compression.) Compressed sensing typically starts with taking a weighted linear combination of samples also called compressive measurements in a basis different from the basis in which the signal is known to be sparse. The results found by David Donoho, Emmanuel Candès, Justin Romberg and Terence Tao showed that the number of these compressive measurements can be small and still contain all the useful information. Therefore, the task of converting the image back into the intended domain involves solving an underdetermined matrix equation since the number of compressive measurements taken is smaller than the number of pixels in the full image. However, adding the constraint that the initial signal is sparse enables one to solve this underdetermined system of linear equations. The classical solution to such problems is to minimize the L2 norm—that is, minimize the amount of energy in the system. This is usually simple mathematically (involving only a matrix multiplication by the pseudo-inverse of the basis sampled in). However, this leads to poor results for most practical applications, as the unknown coefficients seldom have zero energy. In order to enforce the sparsity constraint when solving for the underdetermined system of linear equations, one should be minimizing the L0 norm, or equivalently maximizing the number of zero coefficients in the new basis. However, searching a solution with this constraint is NP-hard (it contains the subset-sum problem), and so is computationally infeasible for all but the tiniest data sets. Following Tao et al., where it was shown that the L1 norm is equivalent the L0 norm, leads one to solve an easier problem. Finding the candidate with the smallest L1 norm can be expressed relatively easily as a linear program, for which efficient solution methods already exist. These solution methods have been refined over the past few years yielding enormous gain. A more technical insight on the different techniques employed in sampling and decoding signals with compressive sensing can be gained in.

The field of compressive sensing has direct connections to Group Testing, Heavy-hitters, Sparse Coding, Multiplexing, Sparse Sampling, Finite Rate of Innovation. Imaging techniques having a strong affinity with compressive sensing include Coded aperture and Computational Photography. As a generic rule of thumb, any two stage techniques or indirect imaging involving the use of a computer for the reconstruction of a signal or an image is bound to find a use for compressive sensing techniques.
Starting with the famous single-pixel camera from Rice University an up-to-date list of the most recent implementations of compressive sensing in hardware at different technology readiness level is listed in. Some hardware implementation like the one used in MRI or Compressed Genotyping do not require an actual physical change whereas other hardware require substantial re-engineering to perform this new type of sampling. Similarly, a number of hardware implementation already existed before 2004 but while they were acquiring signals in a compressed manner, they generally did not use compressive sensing reconstruction techniques to reconstruct the original signal. The result of these reconstruction were suboptimal and have been greatly enhanced thanks to compressive sensing. Hence there is a large disparity of implementation of compressive sensing in different areas of engineering and science.

Compressed Sensing was initially featured in the news as part of the Single-pixel camera from Rice University. Some aspect of Compressed Sensing was featured in Wired's Engineers Test Highly Accurate Face Recognition. A more recent article in Wired described Compressed Sensing as a full fledged technique in Using Math to Turn Lo-Res Datasets Into Hi-Res Samples. Because the article was talking about sampling for MRI, some confusion might have occurred and was addressed in and in.