A survey on one-bit compressed sensing: theory and applications

Abstract

In the past few decades, with the growing popularity of compressed sensing (CS) in the signal processing field, the quantization step in CS has received significant attention. Current research generally considers multi-bit quantization. For systems employing quantization with a sufficient number of bits, a sparse signal can be reliably recovered using various CS reconstruction algorithms.

Recently, many researchers have begun studying the onebit case for CS. As an extreme case of CS, onebit CS preserves only the sign information of measurements, which reduces storage costs and hardware complexity. By treating one-bit measurements as sign constraints, it has been shown that sparse signals can be recovered using certain reconstruction algorithms with a high probability. Based on the merits of one-bit CS, it has been widely applied to many fields, such as radar, source location, spectrum sensing, and wireless sensing network.

In this paper, the characteristics of one-bit CS and related works are reviewed. First, the framework of one-bit CS is introduced. Next, we summarize existing reconstruction algorithms. Additionally, some extensions and practical applications of one-bit CS are categorized and discussed. Finally, our conclusions and the further research topics are summarized.

Keywords

compressed sensing / one-bit quantization / sign information / support / consistency

References

[1] Donoho D L. Compressed sensing. IEEE Transanctions on Information Theory, 2006, 52(4): 1289–1306

[2] Lexa M A, Davies M E, Thompson J S. Reconciling compressive sampling systems for spectrally sparse continuous-time signals. IEEE Transactions on Signal Processing, 2012, 60(1): 155–171

[3] Xu W B, Li Z L, Tian Y, Wang Y, Lin J R. Perturbation analysis of simultaneous orthogonal matching pursuit. Signal Processing, 2015, 116(C): 91–100

[4] Gao K, Batalama S N, Pados D A, Suter B W. Compressive sampling with generalized polygons. IEEE Transactions on Signal Processing, 2011, 59(10): 4759–4766

[5] Laska J N, Baraniuk R G. Regime change: bit-depth versus measurement-rate in compressive sensing. IEEE Transactions on Signal Processing, 2012, 60(7): 3496–3505

[6] Jacques L, Laska J N, Boufounos P T, Baraniuk R G. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory, 2011, 59(4): 2082–2102

[7] Baraniuk R, Foucart S, Needell D, Plan Y, Wootters M. Exponential decay of reconstruction error from binary measurements of sparse signals. arXiv preprint, arXiv:1407.8246, 2014

[8] Knudson K, Saab R, Ward R. One-bit compressive sensing with norm estimation. IEEE Transactions on Information Theory, 2014, 62(5): 2748–2758

[9] Plan Y, Vershynin R. Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach. IEEE Transactions on Information Theory, 2013, 59(1): 482–494

[10] Ai A, Lapanowski A, Plan Y, Vershynin R. One-bit compressed sensing with non-gaussian measurements. Linear Algebra & Its Applications, 2014, 441(1): 222–239

[11] Fang J, Shen Y, Li H. One-bit quantization design and adaptive methods for compressed sensing. Mathematics, 2013

[12] Boufounos P T, Baraniuk R G. 1-bit compressive sensing. In: Proceedings of the 42nd Annual Conference on Information Sciences and Systems. 2008, 16–21

[13] Hale E T, Yin W, Zhang Y. A fixed-point continuation method for l1-regularized minimization with applications to compressed sensing. CAAM Technical Report TR07-07. 2007

[14] Laska J N, Wen Z, Yin W, Baraniuk R G. Trust, but verify: fast and accurate signal recovery from 1-bit compressive measurements. IEEE Transactions on Signal Processing, 2011, 59(11): 5289–5301

[15] Boufounos P T. Greedy sparse signal reconstruction from sign measurements. In: Proceedings of the Conference Record of the 43rd Asilomar Conference on Signals, Systems and Computers. 2009, 1305–1309

[16] Yan M, Yang Y, Osher S. Robust 1-bit compressive sensing using adaptive outlier pursuit. IEEE Transanctions on Signal Processing, 2012, 60(7): 3868–3875

[17] Movahed A, Panahi A, Durisi G. A robust rfpi-based 1-bit compressive sensing reconstruction algorithm. In: Proceedings of the IEEE Information Theory Workshop. 2012, 567–571

[18] Yang Z, Xie L, Zhang C. Variational bayesian algorithm for quantized compressed sensing. IEEE Transactions on Signal Processing, 2013, 61(11): 2815–2824

[19] Li F W, Fang J, Li H B, Huang L. Robust one-bit Bayesian compressed sensing with sign-flip errors. IEEE Signal Processing Letters, 2015, 22(7): 857–861

[20] Zhou T Y, Tao D C. 1-bit hamming compressed sensing. In: Proceedings of IEEE International Symposium on Information Theory Proceedings. 2012, 1862–1866

[21] Tian Y, Xu W B, Wang Y, Yang H W. A distributed compressed sensing scheme based on one-bit quantization. In: Proceedings of the 79th Vehicular Technology Conference. 2014, 1–6

[22] Xiong J P, Tang Q H, Zhao J. 1-bit compressive data gathering for wireless sensor networks. Journal of Sensors, 2014, 2014(7): 177–183

[23] Shen Y N, Fang J, Li H B. One-bit compressive sensing and source location is wireless sensor networks. In: Proceedings of IEEE China Summit and International Conference on Signal and Information Processing. 2013, 379–383

[24] Feng C, Valaee S, Tan Z H. Multiple target localization using compressive sensing. In: Proceedings of IEEE Global Telecommunications Conference. 2009, 1–6

[25] Chen C H, Wu J Y. Amplitude-aided 1-bit compressive sensing over noisy wireless sensor networks. IEEE Wireless Communications Letters, 2015, 4(5): 473–476

[26] Meng J, Li H S, Han Z. Sparse event detection in wireless sensor neworks using compressive sensing. In: Proceedings of the 43rd Annual Conference on Information Sciences and Systems. 2009, 181–185

[27] Sakdejayont T, Lee D, Peng Y, Yamashita Y, Morikawa H. Evaluation of memory-efficient 1-bit compressed sensing in wireless sensor networks. In: Proceedings of the Hummanitarian Technologhy Conference. 2013, 326–329

[28] Lee D, Sasaki T, Yamada T, Akabane K, Yamaguchi Y, Uehara K. Spectrum sensing for networked system using 1-bit compressed sensing with partial random circulant measurement matrices. In: Proceedings of the Vehicular Technology Conference. 2012, 1–5

[29] Fu N, Yang L, Zhang J C. Sub-nyquist 1 bit sampling system for sparse multiband signals. In: Proceedings of the 22nd European Signal Processing Conference. 2014, 736–740

[30] Alberti G, Franceschetti G, Schirinzi G, Pascazio V. Time-domain convolution of one-bit coded radar signals. IEE Proceedings F- Radar and Signal Processing, 1991, 138(5): 438–444

[31] Franceschetti G, Merolla S, Tesauro M. Phase quantized sar signal processing: Theory and experiments. IEEE Transactions on Aerospace and Electronic Systems, 1999, 35(1): 201–214

[32] Dong X, Zhang Y H. A map approach for 1-bit compressive sensing in synthetic aperture radar imaging. IEEE Geoscience and Remote Sensing Letters, 2015, 12(6): 1237–1241

[33] Allstot E G, Chen A Y, Dixon A M R, Gangopadhyay D, Mitsuda H, Allstot D J. Compressed sensing of ECG bio-signals using one-bit measurement matrices. In: Proceedings of the 9th IEEE International New Circuits and Systems Conference. 2011, 213–216

[34] Haboba J, Mangia M, Rovatti R, Setti G. An architecture for 1-bit localized compressive sensing with applications to eeg. In: Proceedings of IEEE Biomedical Circuits and Systems Conference. 2011, 137–140

[35] Candes E J. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 2008, 346(9–10): 589–592

[36] Wright S J, Nowak R D, Figueiredo M A T. Sparse reconstruction by separable approximation. IEEE Transactions on Signal Processing, 2009, 57(7): 2479–2493

[37] Kaasschieter E F. Preconditioned conjugate gradients for solving singular systems. Journal of Computational and Applied Mathematics, 1988, 24(1–2): 265–275

[38] Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 2009, 27(3): 265–274

[39] Pati Y C, Rezaiifar R, Krishnaprasad P S. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In: Proceedings of the 27th Asilomar Conference on Signals, Systems and Computers. 1993, 40–44

[40] Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Foundations of Computational Mathematics, 2009, 9(3): 317–334

[41] Needell D, Tropp J A. Cosamp: iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 2009, 26(3): 301–321

[42] Do T T, Lu G, Nguyen N, Tran T D. Sparsity adaptive matching pursuit algorithm for practical compressed sensing. In: Proceedings of the 42nd Asilomar Conference on Signals, Systems and Computers. 2008, 581–587

[43] Ji S H, Xue Y, Carin L. Bayesian compressive sensing. IEEE Transactions on Signal Processing, 2008, 56(6): 2346–2356

[44] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM Review, 2001, 43(1): 129–159

[45] Tibshirani R. Regression shrinkage and selection via the lasso: a retrospective. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2011, 73(3): 273–282

[46] Candes E J, Romberg J K, Tao T. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 2006, 59(8): 1207–1223

[47] Shen Y, Fang J, Li H, Chen Z. A one-bit reweighted iterative algorithm for sparse signal recovery. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing. 2013, 5915–5919

[48] Zhang L J, Yi J F, Jin R. Efficient algorithms for robust one-bit compressive sensing. In: Proceedings of the 31st International Conference on Machine Learning. 2014, 820–828

[49] Wang H, Wan Q. One bit support recovery. In: Proceedings of the 6th International Conference on Wireless Communications Networking and Mobile Computing. 2010, 1–4

[50] Plan Y, Vershynin R. One-bit compressed sensing by linear programming. Communications on Pure and Applied Mathematics, 2013, 66(8): 1275–1297

[51] North P, Needell D. One-bit compressive sensing with partial support. In: Proceedings of the 6th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2015, 349–352

[52] Fu X, Han F M, Zou H X. Robust 1-bit compressive sensing against sign flips. In: Proceedings of IEEE Global Communications Conference. 2014, 3121–3125

[53] Zayyani H, Korki M, Marvasti F. Dictionary learning for blind one bit compressed sensing. IEEE Signal Processing Letters, 2016, 23(2): 187–191

[54] Huang X L, Shi L, Yan M, Suykens J A K. Pinball loss minimization for one-bit compressive sensing. Mathematics, 2015

[55] Yan M. Restoration of images corrupted by impulse noise and mixed gaussian impulse noise using blind inpainting. SIAM Journal on Imaging Sciences, 2013, 6(3): 1227–1245

[56] Tipping M. Sparse bayesian learning and the relevance vector machine. Journal of Machine Learning Research, 2001, 1(3): 211–244

[57] Chen S, Banerjee A. One-bit compressed sensing with the k-support norm. In: Proceedings of the 18th International Conference on Artificial Intelligence and Statistics. 2015, 138–146

[58] Zhou T Y, Tao D C. k-bit hamming compressed sensing. In: Proceedings of IEEE International Symposium on Information Theory. 2013, 679–683

[59] Baron D, Wakin M B, Duarte M F, Sarvotham S, Baraniuk R G. Distributed compressed sensing. Preprint, 2012, 22(10): 2729–2732

[60] Yin H P, Li J X, Chai Y, Yang S X. A survey on distributed compressed sensing theory and applications. Frontiers of Computer Science, 2014, 8(6): 893–904

[61] Tian Y, Xu W B, Wang Y, Yang H W. Joint reconstruction algorithms for one-bit distributed compressed sensing. In: Proceedings of the 22nd International Conference on Telecommunications. 2015, 338–342

[62] Nakarmi U, Rahnavard N. Joint wideband spectrum sensing in frequency overlapping cognitive radio networks using distributed compressive sensing. In: Proceedings of the Military Communications Conference. 2011, 1035–1040

[63] Li Z L, Xu W B, Wang Y, Lin J R. A tree-based regularized orthogonal matching pursuit algorithm. In: Proceedings of the 22nd International Conference on Telecommunications. 2015, 343–347

[64] He L H, Carin L. Exploiting structure in wavelet-based bayesian compressive sensing. IEEE Transactions on Signal Processing, 2009, 57(9): 3488–3497

[65] Allstot E G, Chen A Y, Dixon A M R, Gangopadhyay D. Compressive sampling of ecg bio-signals: quantization noise and sparsity considerations. In: Proceedings of the IEEE Biomedical Circuits and Systems Conference. 2010, 41–44

[66] Haboba J, Rovatti R, Setti G. Rads converter: an approach to analog to information conversion. In: Proceedings of the 19th IEEE International Conference on Electronics, Circuits and Systems. 2012, 49–52

[67] Movahed A, Reed M C. Iterative detection for compressive sensing: Turbo cs. In: Proceedings of IEEE International Conference on Communications. 2014, 4518–4523

[68] Yamada T, Lee D, Toshinaga H, Akabane K, Yamaguchi Y, Uehara K. 1-bit compressed sensing with edge detection for compressed radio wave data transfer. In: Proceedings of the 18th Asia-Pacific Conference on Communications. 2012, 407–411

[69] Mo J, Schniter P, Prelcic N G, Heath R W. Channel estimation in millimeter wave mimo systems with one-bit quantization. In: Proceedings of the 48th Asilomar Conference on Signals, Systems and Computers. 2014, 957–961

[70] Luo C. A low power self-capacitive touch sensing analog front end with sparse multi-touch detection. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing. 2014, 3007–3011

[71] Chen H, Shao H. Sparse recovery-based doa estimator with signaldependent dictionary. In: Proceedings of the 8th International Conference on Signal Processing and Communication Systems. 2014, 1–4

[72] Gupta A, Nowak R, Recht B. Sample complexity for 1-bit compressed sensing and sparse classification. In: Proceedings of IEEE International Symposium on Information Theory Proceedings. 2010, 1553–1557

[73] Candes E, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): 489–509

[74] Rauhut H. Circulant and toeplitz matrices in compressed sensing. Mathematics, 2009

[75] Candes E J, Wakin M B. An introduction to compressive sampling. IEEE Signal Processing Magzine, 2008, 25(2): 21–30

[76] Candes E, Tao T. Decoding by linear programming. IEEE Transactions on Information Theory, 2005, 51(12): 4203–4215

[77] Scarlett J, Evans J S, Dey S. Compressed sensing with prior information: information-theoretic limits and practical decoders. IEEE Transactions on Signal Processing, 2013, 61(2): 427–439

[78] Eldar Y C, Kuppinger P, Bolcskei H. Compressed sensing of blocksparse signals: uncertainty relations and efficient recovery. IEEE Transactions on Signal Processing, 2010, 58(6): 3042–3054

[79] Yu X H, Baek S J. Sufficient conditions on stable recovery of sparse signals with partial support information. IEEE Signal Processing Letters, 2013, 20(5): 539–542

[80] Friedlander M P, Mansour H, Saab R, Yilmaz O. Recovering compressively sampled signals using partial support information. IEEE Transactions on Information Theory, 2012, 58(2): 1122–1134

[81] Miosso C J, Borries R V, Pierluissi J H. Compressive sensing with prior information: requirements and probabilities of reconstruction in l1- minimization. IEEE Transactions on Signal Processing, 2013, 61(9): 2150–2164

[82] Davenport M A, Wakin M B. Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Transactions on Information Theory, 2010, 56(9): 4395–4401

[83] Liu E, Temlyakov V N. The orthogonal super greedy algorithm and applications in compressed sensing. IEEE Transactions on Information Theory, 2012, 58(4): 2040–2047

[84] Ding J, Chen L M, Gu Y T. Perturbation analysis of orthogonal matching pursuit. IEEE Transactions on Signal Processing, 2013, 61(2): 398–410

[85] Mo Q, Shen Y. A remark on the restricted isometry property in orthogonal matching pursuit. IEEE Transactions on Infirmation Theroy, 2012, 58(6): 3654–3656

[86] Maleh R. Improved RIP analysis of orthogonal matching pursuit. Computer Science, 2011

[87] Dai W, Milenkovic O. Subspace pursuit for compressive sensing: Closing the gap between performance and complexity. IEEE Transactions on Infirmation Theroy, 2008, 55(5): 2230–2249

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature