Sparse Signal Sampling using Noisy Linear Projections

: In many engineering applications we choose to view the world (an unknown signal) through a set of samples. Often, a relatively small number of samples tells us all we need to know. For example, the classical Whittaker-Nyquist-Kotelnikov-Shannon sampling theorem states that a continuous-time band-limited signal can be perfectly reconstructed from uniformly spaced discrete samples provided that the sampling rate (number of samples per time) is greater than twice the signal bandwidth. This fact is crucial to the analog-to-digital conversion in signal processing and telecommunications. For a more general notion of what it means to sample a signal, we may consider a variety of interesting applications where the signals of interest are not band-limited. In fact, even more can be said when we consider that sometimes the information we desire is not an unknown signal per se, but rather some function of it. Examples from the past decade include spectrum blind sampling (Bresler et al. [1, 2, 3]), sampling with a finite rate of innovation (Vetterli et al [4]) and compressed sensing (Donoho [5] and Candes & Tao [6], and many others). In particular, the field of compressed sensing deals with the digital-to-digital sampling of signals that are somehow compressible. For many such signals, the sampling processes simultaneously senses (provides a set of samples sufficient to reconstruct an unknown signal) and compresses (the number of samples is far less than the dimension of the original signal).