TY - JOUR

T1 - Beyond Nyquist

T2 - Efficient sampling of sparse bandlimited signals

AU - Tropp, Joel A.

AU - Laska, Jason N.

AU - Duarte, Marco F.

AU - Romberg, Justin K.

AU - Baraniuk, Richard G.

N1 - Funding Information:
Manuscript received January 31, 2009; revised September 18, 2009. Current version published December 23, 2009. The work of J. A. Tropp was supported by ONR under Grant N00014-08-1-0883, DARPA/ONR under Grants N66001-06-1-2011 and N66001-08-1-2065, and NSF under Grant DMS-0503299. The work of J. N. Laska, M. F. Duarte, and R. G. Bara-niuk was supported by DARPA/ONR under Grants N66001-06-1-2011 and N66001-08-1-2065, ONR under Grant N00014-07-1-0936, AFOSR under Grant FA9550-04-1-0148, NSF under Grant CCF-0431150, and the Texas Instruments Leadership University Program. The work of J. K. Romberg was supported by NSF under Grant CCF-515632. The material in this paper was presented in part at SampTA 2007, Thessaloniki, Greece, June 2007.

PY - 2010/1

Y1 - 2010/1

N2 - Wideband analog signals push contemporary analog-to-digital conversion (ADC) systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient because the signals of interest contain only a small number of significant frequencies relative to the band limit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its band limit in hertz. Simulations suggest that the random demodulator requires just O(K log(W/K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W hertz. In contrast to Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. This paper provides a detailed theoretical analysis of the system's performance that supports the empirical observations.

AB - Wideband analog signals push contemporary analog-to-digital conversion (ADC) systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient because the signals of interest contain only a small number of significant frequencies relative to the band limit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its band limit in hertz. Simulations suggest that the random demodulator requires just O(K log(W/K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W hertz. In contrast to Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. This paper provides a detailed theoretical analysis of the system's performance that supports the empirical observations.

KW - Analog-to-digital conversion

KW - Compressive sampling

KW - Sampling theory

KW - Signal recovery

KW - Sparse approximation

UR - http://www.scopus.com/inward/record.url?scp=73849142717&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73849142717&partnerID=8YFLogxK

U2 - 10.1109/TIT.2009.2034811

DO - 10.1109/TIT.2009.2034811

M3 - Article

AN - SCOPUS:73849142717

SN - 0018-9448

VL - 56

SP - 520

EP - 544

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 1

M1 - 5361485

ER -