Compressed sensing

Compressed sensing (CS) was motivated in part by the desire to sample wideband signals at rates far lower than the Shannon–Nyquist rate, while still maintaining the essential information encoded in the underlying signal.

A common approach in engineering is to assume that the signal is bandlimited, meaning that the spectral contents are confined to a maximal frequency.

Bandlimited signals have limited time variation, and can therefore be perfectly reconstructed from equispaced samples with rate at least 2B, termed the Nyquist rate.

Conversion speeds which are twice the signal’s maximal frequency component have become more and more difficult to obtain.

A common practice in engineering is demodulation in which the input signal is multiplied by the carrier frequency of a band of interest, in order to shift the contents of the narrowband transmission from the high frequencies to the origin.

A “holy grail” of CS is to build acquisition devices that exploit signal structure in order to reduce the sampling rate, and subsequent demands on storage and DSP. In such an approach, the actual information contents dictate the sampling rate, rather than the dimensions of the ambient space in which the signal resides.

At its core, CS is a mathematical framework that studies accurate recovery of a signal represented by a vector of length from M << N measurements, effectively performing compression during signal acquisition.

The measurement paradigm consists of linear projections, or inner products, of the signal vector
into a set of carefully chosen projection vectors that act as a multitude of probes on the information contained in the signal.

In CS we do not acquire x directly but rather acquire M < N linear measurements y=phi*x using an M*N CS matrix phi.

y is the measurement vector. Ideally, the matrix phi is designed to reduce the number of measurements M as much as possible while allowing for recovery of a wide class of signals x from their measurement vectors y.

For any particular signal x_0 in R^N, an infinite number of signals x will produce the same measurements y_0= phi * x_0 = phi * x for the chosen CS matrix phi.

Sparsity is the signal structure behind many compression algorithms that employ transform coding, and is the most prevalent signal structure used in CS.

References
Marco F. Duarte and Yonina C. Eldar, Structured Compressed Sensing-From Theory to Applications, IEEE Transactions On Signal Processing, September 2011