Summary: Introduction to compressive sensing. This course introduces the basic concepts in compressive sensing. We overview the concepts of sparsity, compressibility, and transform coding. We then review applications of sparsity in several signal processing problems such as sparse recovery, model selection, data coding, and error correction. We overview the key results in these fields, focusing primarily on both theory and algorithms for sparse recovery. We also discuss applications of compressive sensing in communications, biosensing, medical imaging, and sensor networks.
We are in the midst of a digital revolution that is driving the development and deployment of new kinds of sensing systems with ever-increasing fidelity and resolution. The theoretical foundation of this revolution is the pioneering work of Kotelnikov, Nyquist, Shannon, and Whittaker on sampling continuous-time band-limited signals [14], [15], [18], [21]. Their results demonstrate that signals, images, videos, and other data can be exactly recovered from a set of uniformly spaced samples taken at the so-called Nyquist rate of twice the highest frequency present in the signal of interest. Capitalizing on this discovery, much of signal processing has moved from the analog to the digital domain and ridden the wave of Moore's law. Digitization has enabled the creation of sensing and processing systems that are more robust, flexible, cheaper and, consequently, more widely-used than their analog counterparts.
As a result of this success, the amount of data generated by sensing systems has grown from a trickle to a torrent. Unfortunately, in many important and emerging applications, the resulting Nyquist rate is so high that we end up with far too many samples. Alternatively, it may simply be too costly, or even physically impossible, to build devices capable of acquiring samples at the necessary rate. Thus, despite extraordinary advances in computational power, the acquisition and processing of signals in application areas such as imaging, video, medical imaging, remote surveillance, spectroscopy, and genomic data analysis continues to pose a tremendous challenge.
To address the logistical and computational challenges involved in dealing with such high-dimensional data, we often depend on compression, which aims at finding the most concise representation of a signal that is able to achieve a target level of acceptable distortion. One of the most popular techniques for signal compression is known as transform coding, and typically relies on finding a basis or frame that provides sparse or compressible representations for signals in a class of interest. By a sparse representation, we mean that for a signal of length
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 than suggested 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 [1], [5], [10]. 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 [16]. The next theoretical leap came in the early 1900's, when Carathéodory showed that a positive linear combination of any
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 [2]. 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
More recently, Candès, Romberg, Tao [5], [6], [7], [8], [9], and Donoho [10] 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 [19]. 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,
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.
More about this module: Metadata | Downloads | Version History
This work is licensed by Mark A. Davenport, Marco F. Duarte, Chinmay Hegde, and Richard Baraniuk under a Creative Commons Attribution License (CC-BY 3.0), and is an Open Educational Resource.
Last edited by Jared Adler on Apr 10, 2011 12:23 am -0500.
