Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994 · see citing works
Donoho, D. L. (2004) · Cited by 17,049 · see citing works
A Wavelet Tour of Signal Processing
Mallat, S. (1999) · Elsevier eBooks · doi:10.1016/b978-0-12-466606-1.x5000-4 · Cited by 16,383 · see citing works
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639 · see citing works
Self-citationDiscrete-Time Signal Processing
Oppenheim, A. V., & Schafer, R. W. (1989) · Cited by 11,808 · see citing works
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Tropp, J. A., & Gilbert, A. C. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.909108 · Cited by 9,828 · see citing works
Self-citationStable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036 · see citing works
Self-citationNear-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candès, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,973 · see citing works
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,734 · see citing works
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Matsumoto, M., & Nishimura, T. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.272995 · Cited by 5,780 · see citing works
Discrete-time Signal Processing
Williamson, D. (1999) · Advanced textbooks in control and signal processing · doi:10.1007/978-1-4471-0541-1 · Cited by 4,895 · see citing works
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Needell, D., & Tropp, J. A. (2008) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2008.07.002 · Cited by 4,449 · see citing works
Self-citationFigueiredo, M. A. T., Nowak, R. D., & Wright, S. J. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910281 · Cited by 3,531 · see citing works
Numerical Methods for Least Squares Problems
Björck, Å. (1996) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971484 · Cited by 3,276 · see citing works
Numerical methods for least squares problems
Björck, Å. (1996) · Choice Reviews Online · doi:10.5860/choice.34-1602 · Cited by 3,067 · see citing works
Implementation issues in spectrum sensing for cognitive radios
Čabrić, D. B., Mishra, S. M., & Brodersen, R. W. (2005) · 2018 52nd Asilomar Conference on Signals, Systems, and Computers · doi:10.1109/acssc.2004.1399240 · Cited by 2,606 · see citing works
A Simple Proof of the Restricted Isometry Property for Random Matrices
Baraniuk, R. G., Davenport, M. A., DeVore, R., & Wakin, M. B. (2008) · Constructive Approximation · doi:10.1007/s00365-007-9003-x · Cited by 2,310 · see citing works
Self-citationAnalog-to-digital converter survey and analysis
Walden, R. H. (1999) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.761034 · Cited by 2,186 · see citing works
Sparsity and incoherence in compressive sampling
Candès, E. J., & Romberg, J. K. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/008 · Cited by 2,109 · see citing works
Self-citationLedoux, M., & Talagrand, M. (1991) · Springer eBooks · doi:10.1007/978-3-642-20212-4 · Cited by 1,469 · see citing works
Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/070703983 · Cited by 1,413 · see citing works
Iteratively reweighted least squares minimization for sparse recovery
Daubechies, I. C., DeVore, R., Fornasier, M., & Güntürk, C. S. (2009) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20303 · Cited by 1,295 · see citing works
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
Mishali, M., & Eldar, Y. C. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042414 · Cited by 1,188 · see citing works
High-Resolution Radar via Compressed Sensing
Herman, M. A., & Strohmer, T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2014277 · Cited by 1,071 · see citing works
Sampling signals with finite rate of innovation
Vetterli, M., Marziliano, P., & Blu, T. (2002) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2002.1003065 · Cited by 1,071 · see citing works
Compressed sensing and best 𝑘-term approximation
Cohen, A., Dahmen, W., & DeVore, R. (2008) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-08-00610-3 · Cited by 1,048 · see citing works
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit
Needell, D., & Vershynin, R. (2008) · Foundations of Computational Mathematics · doi:10.1007/s10208-008-9031-3 · Cited by 965 · see citing works
Grassmannian frames with applications to coding and communication
Strohmer, T., & Heath, R. W. (2003) · Applied and Computational Harmonic Analysis · doi:10.1016/s1063-5203(03)00023-x · Cited by 920 · see citing works
Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
Hale, E. T., Yin, W., & Zhang, Y. (2008) · SIAM Journal on Optimization · doi:10.1137/070698920 · Cited by 911 · see citing works
Baraniuk, R. G., & Steeghs, P. (2007) · Proceedings of the IEEE National Radar Conference · doi:10.1109/radar.2007.374203 · Cited by 905 · see citing works
Self-citationNESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2009) · Cited by 897 · see citing works
Necessary density conditions for sampling and interpolation of certain entire functions
Landau, H. J. (1967) · Acta Mathematica · doi:10.1007/bf02395039 · Cited by 874 · see citing works
Needell, D., & Vershynin, R. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2042412 · Cited by 854 · see citing works
Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals
Mishali, M., & Eldar, Y. C. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2012791 · Cited by 831 · see citing works
Simple Constructions of Almost k‐wise Independent Random Variables
Alon, N., Goldreich, O., Håstad, J., et al. (1992) · Random Structures and Algorithms · doi:10.1002/rsa.3240030308 · Cited by 561 · see citing works
Sampling, data transmission, and the Nyquist rate
Landau, H. J. (1967) · Proceedings of the IEEE · doi:10.1109/proc.1967.5962 · Cited by 505 · see citing works
Compressive Sensing by Random Convolution
Romberg, J. K. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/08072975x · Cited by 466 · see citing works
Self-citationToeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
Haupt, J., Bajwa, W. U., Raz, G. M., et al. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2070191 · Cited by 433 · see citing works
Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang–Fix
Dragotti, P. L., Vetterli, M., & Blu, T. (2007) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.890907 · Cited by 428 · see citing works
Sparse Sampling of Signal Innovations
Blu, T., Dragotti, P. L., Vetterli, M., Marziliano, P., & Coulot, L. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914998 · Cited by 425 · see citing works
Data compression and harmonic analysis
Donoho, D. L., Vetterli, M., DeVore, R., & Daubechies, I. C. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720544 · Cited by 424 · see citing works
Theory and Implementation of an Analog-to-Information Converter using Random Demodulation
Laska, J. N., Kirolos, S., Duarte, M. F., et al. (2007) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2007.378360 · Cited by 422 · see citing works
Self-citationAnalog-to-Information Conversion via Random Demodulation
Kirolos, S., Laska, J., Wakin, M., Duarte, M., Baron, D., Ragheb, T., Massoud, Y., & Baraniuk, R. (2006) · 2006 IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software · doi:10.1109/dcas.2006.321036 · Cited by 393 · see citing works
Self-citationHigh-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension
Donoho, D. L. (2005) · Discrete & Computational Geometry · doi:10.1007/s00454-005-1220-0 · Cited by 378 · see citing works
Le, B., Rondeau, T. W., Reed, J. H., et al. (2005) · IEEE Signal Processing Magazine · doi:10.1109/msp.2005.1550190 · Cited by 354 · see citing works
The best constants in the Khintchine inequality
Haagerup, U. (1981) · Studia Mathematica · doi:10.4064/sm-70-3-231-283 · Cited by 350 · see citing works
Learning Decision Trees Using the Fourier Spectrum
Eyal Kushilevitz, Z., & Mansour, Y. (1993) · SIAM Journal on Computing · doi:10.1137/0222080 · Cited by 325 · see citing works
Venkataramani, R., & Bresler, Y. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.868487 · Cited by 305 · see citing works
Spectrum-blind minimum-rate sampling and reconstruction of multiband signals
Feng, P., & Bresler, Y. (2002) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1996.544131 · Cited by 284 · see citing works
Near-optimal sparse fourier representations via sampling
Gilbert, A. C., Guha, S., Indyk, P., et al. (2002) · doi:10.1145/509907.509933 · Cited by 274 · see citing works
Random Filters for Compressive Sampling and Reconstruction
Tropp, J. A., Wakin, M. B., Duarte, M. F., et al. (2006) · doi:10.1109/icassp.2006.1660793 · Cited by 266 · see citing works
Self-citationSparse reconstruction by convex relaxation: Fourier and Gaussian measurements
Rudelson, M., & Vershynin, R. (2006) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2006.286463 · Cited by 234 · see citing works
Random Sampling for Analog-to-Information Conversion of Wideband Signals
Laska, J. N., Kirolos, S., Massoud, Y., et al. (2006) · doi:10.1109/dcas.2006.321048 · Cited by 229 · see citing works
Self-citationOn the conditioning of random subdictionaries
Tropp, J. A. (2007) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.09.001 · Cited by 220 · see citing works
Self-citationImproved time bounds for near-optimal sparse Fourier representations
Gilbert, A. C., Muthukrishnan, S., & Strauss, M. (2005) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.615931 · Cited by 216 · see citing works
Bourgain, J., & Tzafriri, L. (1987) · Israel Journal of Mathematics · doi:10.1007/bf02772174 · Cited by 209 · see citing works
Curvelet-based seismic data processing: A multiscale and nonlinear approach
Herrmann, F. J., Wang, D., Hennenfent, G., et al. (2007) · Geophysics · doi:10.1190/1.2799517 · Cited by 189 · see citing works
Compressed Sensing of Analog Signals in Shift-Invariant Spaces
Eldar, Y. C. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2020750 · Cited by 166 · see citing works
A Tutorial on Fast Fourier Sampling
Gilbert, A. C., Strauss, M., & Tropp, J. A. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.915000 · Cited by 142 · see citing works
Self-citationCirculant and Toeplitz matrices in compressed sensingPreprint
Rauhut, H. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0902.4394 · Cited by 133 · see citing works
Norms of random submatrices and sparse approximation
Tropp, J. A. (2008) · Comptes Rendus Mathématique · doi:10.1016/j.crma.2008.10.008 · Cited by 81 · see citing works
Self-citationExpression of Concern:Implementation models for analog-to-information conversion via random sampling
Ragheb, T., Kirolos, S., Laska, J. N., et al. (2007) · doi:10.1109/mwscas.2007.4488599 · Cited by 78 · see citing works
Self-citationScientific Computing Kernels on the Cell Processor
Williams, S., Shalf, J. M., Oliker, L., et al. (2007) · International Journal of Parallel Programming · doi:10.1007/s10766-007-0034-5 · Cited by 60 · see citing works
Efficient sampling of sparse wideband analog signals
Mishali, M., Eldar, Y. C., & Tropp, J. A. (2008) · IEEE Convention of Electrical and Electronics Engineers in Israel · doi:10.1109/eeei.2008.4736707 · Cited by 54 · see citing works
Self-citationOn the Linear Independence of Spikes and Sines
Tropp, J. A. (2008) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9042-0 · Cited by 45 · see citing works
Self-citationAdamczak, R. (2005) · Bulletin of the Polish Academy of Sciences Mathematics · doi:10.4064/ba53-2-10 · Cited by 40 · see citing works
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurementsPreprint
Rudelson, M., & Vershynin, R. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0602559 · Cited by 38 · see citing works
Near-optimal sparse fourier representations via sampling
Gilbert, A. C., Guha, S., Indyk, P., et al. (2002) · doi:10.1145/509931.509933 · Cited by 27 · see citing works
Perfect Reconstruction Schemes for Sampling Piecewise Sinusoidal Signals
Berent, J., & Dragotti, P. L. (2006) · doi:10.1109/icassp.2006.1660669 · Cited by 8 · see citing works
Data Compression and Harmonic Analysis
(2009) · Institute of Electrical and Electronics Engineers eBooks · doi:10.1109/9780470544907.ch15 · Cited by 6 · see citing works
Flagged first, then by citations
Research works printed but not linked: 5
- [10][10] M. Matsumoto and T. Nishimura, 'Mersenne Twister: A 623dimensionally equidistributed uniform pseudorandom number generator,' ACM Trans. Modeling and Computer Simulation , vol. 8, no. 1, pp. 3-30, Jan. 1998. -
- [30][30] B. Le, T. W. Rondeau, J. Reed, and C. Bostian, 'Analog-to-digital converters: A review of the past, present and future,' IEEE Signal Processing Mag. , 2005. -
- [33][33] W. Yin, S. Osher, J. Darbon, and D. Goldfarb, 'Bregman iterative algorithms for compressed sesning and related problems,' SIAM J. Imaging Sci. , vol. 1, no. 1, pp. 143-168, 2008. -
- [48][48] Y. C. Eldar and M. Mishali, 'Compressed sensing of analog signals in shift-invariant spaces,' IEEE Trans. Inform. Theory , 2009, to appear. -
- [59][59] T. Ragheb, S. Kirolos, J. Laska, A. Gilbert, M. Strauss, R. Baraniuk, and Y. Massoud, 'Implementation models for analog-to-information conversion via random sampling,' in Proc. 2007 Midwest Symp. Circuits and Systems (MWSCAS) , Aug. 2007, pp. 325-328. -
Cited by
Sorted by citations
Sparse Representation for Wireless Communications: A Compressive Sensing Approach
Qin, Z., Fan, J., Liu, Y., Gao, Y., & Li, G. Y. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2789521 · Cited by 247 · see citing works
Yu, Y., Han, F., Bao, Y., & Ou, J. (2016) · IEEE Sensors Journal · doi:10.1109/jsen.2015.2512846 · Cited by 48 · see citing works
Parameter Estimation of SAR Signal Based on SVD for the Nyquist Folding Receiver
Li, T., Zhu, Q., & Chen, Z. (2018) · Sensors · doi:10.3390/s18061768 · Cited by 8 · see citing works
Liu, X., Li, T., Fan, X., & Chen, Z. (2019) · Sensors · doi:10.3390/s19061477 · Cited by 8 · see citing works
“Compared with the Gegenbauer system [5,6] and many other compress sensing (CS) based architectures [10,11] that require full signal reconstruction, the NYFR basically preserves the signal structure, and the information reconstruction can be relatively simple with conventional signal analysis methods [12].”
- Authors
- Tropp, J. A., Laska, J. N., Duarte, M. F., Romberg, J. K., & Baraniuk, R. G.
- Affiliations
- California Institute of Technology (US)
- Rice University (US)
- Princeton University (US)
- Georgia Institute of Technology (US)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2010-01
- Volume
- 56
- Issue
- 1
- Pages
- 520-544
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2141116650
- Cited by
- 1,089
- References
- 70
- Citations by year
- 2026: 11 · 2025: 31 · 2024: 20 · 2023: 38 · 2022: 35 · 2021: 49 · 2020: 60 · 2019: 103 · 2018: 95 · 2017: 86 · 2016: 76 · 2015: 104 · 2014: 94 · 2013: 98 · 2012: 72
- FWCI
- 86.20
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical Analysis and Transform Methods
- Physical Sciences › Computer Science › Signal Processing › Digital Filter Design and Implementation
- Keywords
- random demodulator, sub-Nyquist sampling, band-limited signals, analog-to-digital conversion, signal reconstruction, convex optimization, compressed sensing, data acquisition system
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
