Introduction to compressive sensing

Leveraging the concept of transform coding, compressive sensing (CS) has emerged as a new framework for signal acquisition and sensor design. CS enables a potentially large reduction in the sampling and computation costs for sensing signals that have a sparse or compressible representation. The Nyquist-Shannon sampling theorem states that a certain minimum number of samples is required in order to perfectly capture an arbitrary bandlimited signal, but when the signal is sparse in a known basis we can vastly reduce the number of measurements that need to be stored. Consequently, when sensing sparse signals we might be able to do better thansuggested by classical results. This is the fundamental idea behind CS: rather than first sampling at a high rate and then compressing the sampled data, we would like to find ways to directly sense the data in a compressed form — i.e., at a lower sampling rate. The field of CS grew out of the work of Emmanuel Candès, Justin Romberg, and Terence Tao and of David Donoho, who showed that a finite-dimensional signal having a sparse or compressible representation can be recovered from a small set of linear, nonadaptive measurements  [link] , [link] , [link] . The design of these measurement schemes and their extensions to practical data models and acquisition schemes are one of the most central challenges in the field of CS.

Although this idea has only recently gained significant attraction in the signal processing community, there have been hints in this direction dating back as far as the eighteenth century. In 1795, Prony proposed an algorithm for the estimation of the parameters associated with a small number of complex exponentials sampled in the presence of noise  [link] . The next theoretical leap came in the early 1900's, when Carathéodory showed that a positive linear combination of any $K$ sinusoids is uniquely determined by its value at $t=0$ and at any other $2K$ points in time  [link] , [link] . This represents far fewer samples than the number of Nyquist-rate samples when $K$ is small and the range of possible frequencies is large. In the 1990's, this work was generalized by George, Gorodnitsky, and Rao, who studied sparsity in the context of biomagnetic imaging and other contexts  [link] , [link] , and by Bressler and Feng, who proposed a sampling scheme for acquiring certain classes of signals consisting of $K$ components with nonzero bandwidth (as opposed to pure sinusoids)  [link] , [link] . In the early 2000's Vetterli, Marziliano, and Blu proposed a sampling scheme for non-bandlimited signals that are governed by only $K$ parameters, showing that these signals can be sampled and recovered from just $2K$ samples  [link] .

A related problem focuses on recovery of a signal from partial observation of its Fourier transform. Beurling proposed a method for extrapolating these observations to determine the entire Fourier transform  [link] . One can show that if the signal consists of a finite number of impulses, then Beurling's approach will correctly recover the entire Fourier transform (of this non-bandlimited signal) from any sufficiently large piece of its Fourier transform. His approach — to find the signal with smallest ${\ell }_1$ norm among all signals agreeing with the acquired Fourier measurements — bears a remarkable resemblance to some of the algorithms used in CS.

More recently, Candès, Romberg, Tao  [link] , [link] , [link] , [link] , [link] , and Donoho  [link] showed that a signal having a sparse representation can be recovered exactly from a small set of linear, nonadaptive measurements. This result suggests that it may be possible to sense sparse signals by taking far fewer measurements, hence the name compressive sensing. Note, however, that CS differs from classical sampling in two important respects. First, rather than sampling the signal at specific points in time, CS systems typically acquire measurements in the form of inner products between the signal and more general test functions. We will see throughout this course that randomness often plays a key role in the design of these test functions. Second, the two frameworks differ in the manner in which they deal with signal recovery , i.e., the problem of recovering the original signal from the compressive measurements. In the Nyquist-Shannon framework, signal recovery is achieved through cardinal sine (sinc) interpolation — a linear process that requires little computation and has a simple interpretation.

CS has already had notable impact on several applications. One example is medical imaging , where it has enabled speedups by a factor of seven in pediatric MRI while preserving diagnostic quality  [link] . Moreover, the broad applicability of this framework has inspired research that extends the CS framework by proposing practical implementations for numerous applications, including sub-Nyquist analog-to-digital converters (ADCs), compressive imaging architectures , and compressive sensor networks .

This course introduces the basic concepts in compressive sensing. We overview the concepts of sparsity , compressibility , and transform coding. We overview the key results in the field, beginning by focusing primarily on the theory of sensing matrix design , ${\ell }_1$ -minimization , and alternative algorithms for sparse recovery . We then review applications of sparsity in several signal processing problems such as sparse regression and model selection , error correction , group testing , and compressive inference . We also discuss applications of compressive sensing in analog-to-digital conversion , biosensing , conventional and hyperspectral imaging, medical imaging , and sensor networks .

Acknowledgments

The authors would like to thank Ewout van den Berg, Yonina Eldar, Piotr Indyk, Gitta Kutyniok, and Yaniv Plan for their feedback regarding some portions of this course which now also appear in the introductory chapter of Compressed Sensing: Theory and Applications , Cambridge University Press, 2011.