|
|
A survey on one-bit compressed sensing: theory and applications |
Zhilin LI( ), Wenbo XU, Xiaobo ZHANG, Jiaru LIN |
Key Lab of Universal Wireless Communications,Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, China |
|
|
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
|
Corresponding Author(s):
Zhilin LI
|
Just Accepted Date: 05 January 2017
Online First Date: 06 March 2018
Issue Date: 22 March 2018
|
|
1 |
Donoho D L. Compressed sensing. IEEE Transanctions on Information Theory, 2006, 52(4): 1289–1306
https://doi.org/10.1109/TIT.2006.871582
|
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
https://doi.org/10.1109/TSP.2011.2169408
|
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
https://doi.org/10.1016/j.sigpro.2015.04.009
|
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
https://doi.org/10.1109/TSP.2011.2160860
|
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
https://doi.org/10.1109/TSP.2012.2194710
|
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
https://doi.org/10.1109/TIT.2012.2234823
|
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
https://doi.org/10.1109/TIT.2016.2527637
|
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
https://doi.org/10.1109/TIT.2012.2207945
|
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
https://doi.org/10.1016/j.laa.2013.04.002
|
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
https://doi.org/10.1109/CISS.2008.4558487
|
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
https://doi.org/10.1109/TSP.2011.2162324
|
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
https://doi.org/10.1109/ACSSC.2009.5469926
|
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
https://doi.org/10.1109/TSP.2012.2193397
|
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
https://doi.org/10.1109/ITW.2012.6404739
|
18 |
Yang Z, Xie L, Zhang C. Variational bayesian algorithm for quantized compressed sensing. IEEE Transactions on Signal Processing, 2013, 61(11): 2815–2824
https://doi.org/10.1109/TSP.2013.2256901
|
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
https://doi.org/10.1109/LSP.2014.2373380
|
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
https://doi.org/10.1109/ISIT.2012.6283603
|
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
https://doi.org/10.1109/VTCSpring.2014.7022772
|
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
https://doi.org/10.1155/2014/805423
|
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
https://doi.org/10.1109/GLOCOM.2009.5425808
|
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
https://doi.org/10.1109/LWC.2015.2441702
|
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
https://doi.org/10.1109/R10-HTC.2013.6669064
|
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
https://doi.org/10.1109/VETECS.2012.6240259
|
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
https://doi.org/10.1049/ip-f-2.1991.0057
|
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
https://doi.org/10.1109/7.745692
|
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
https://doi.org/10.1109/LGRS.2015.2390623
|
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
https://doi.org/10.1109/NEWCAS.2011.5981293
|
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
https://doi.org/10.1109/BioCAS.2011.6107746
|
35 |
Candes E J. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 2008, 346(9–10): 589–592
https://doi.org/10.1016/j.crma.2008.03.014
|
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
https://doi.org/10.1109/TSP.2009.2016892
|
37 |
Kaasschieter E F. Preconditioned conjugate gradients for solving singular systems. Journal of Computational and Applied Mathematics, 1988, 24(1–2): 265–275
https://doi.org/10.1016/0377-0427(88)90358-5
|
38 |
Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 2009, 27(3): 265–274
https://doi.org/10.1016/j.acha.2009.04.002
|
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
https://doi.org/10.1109/ACSSC.1993.342465
|
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
https://doi.org/10.1007/s10208-008-9031-3
|
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
https://doi.org/10.1016/j.acha.2008.07.002
|
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
https://doi.org/10.1109/ACSSC.2008.5074472
|
43 |
Ji S H, Xue Y, Carin L. Bayesian compressive sensing. IEEE Transactions on Signal Processing, 2008, 56(6): 2346–2356
https://doi.org/10.1109/TSP.2007.914345
|
44 |
Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM Review, 2001, 43(1): 129–159
https://doi.org/10.1137/S003614450037906X
|
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
https://doi.org/10.1111/j.1467-9868.2011.00771.x
|
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
https://doi.org/10.1002/cpa.20124
|
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
https://doi.org/10.1109/ICASSP.2013.6638799
|
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
https://doi.org/10.1109/WICOM.2010.5600266
|
50 |
Plan Y, Vershynin R. One-bit compressed sensing by linear programming. Communications on Pure and Applied Mathematics, 2013, 66(8): 1275–1297
https://doi.org/10.1002/cpa.21442
|
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
https://doi.org/10.1109/CAMSAP.2015.7383808
|
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
https://doi.org/10.1109/GLOCOM.2014.7037285
|
53 |
Zayyani H, Korki M, Marvasti F. Dictionary learning for blind one bit compressed sensing. IEEE Signal Processing Letters, 2016, 23(2): 187–191
https://doi.org/10.1109/LSP.2015.2503804
|
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
https://doi.org/10.1137/12087178X
|
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
https://doi.org/10.1109/ISIT.2013.6620312
|
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
https://doi.org/10.1007/s11704-014-3461-7
|
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
https://doi.org/10.1109/ICT.2015.7124707
|
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
https://doi.org/10.1109/MILCOM.2011.6127433
|
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
https://doi.org/10.1109/ICT.2015.7124708
|
64 |
He L H, Carin L. Exploiting structure in wavelet-based bayesian compressive sensing. IEEE Transactions on Signal Processing, 2009, 57(9): 3488–3497
https://doi.org/10.1109/TSP.2009.2022003
|
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
https://doi.org/10.1109/BIOCAS.2010.5709566
|
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
https://doi.org/10.1109/ICECS.2012.6463560
|
67 |
Movahed A, Reed M C. Iterative detection for compressive sensing: Turbo cs. In: Proceedings of IEEE International Conference on Communications. 2014, 4518–4523
https://doi.org/10.1109/ICC.2014.6884033
|
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
https://doi.org/10.1109/APCC.2012.6388170
|
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
https://doi.org/10.1109/ACSSC.2014.7094595
|
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
https://doi.org/10.1109/ICASSP.2014.6854152
|
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
https://doi.org/10.1109/ISIT.2010.5513510
|
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
https://doi.org/10.1109/TIT.2005.862083
|
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
https://doi.org/10.1109/MSP.2007.914731
|
76 |
Candes E, Tao T. Decoding by linear programming. IEEE Transactions on Information Theory, 2005, 51(12): 4203–4215
https://doi.org/10.1109/TIT.2005.858979
|
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
https://doi.org/10.1109/TSP.2012.2225051
|
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
https://doi.org/10.1109/TSP.2010.2044837
|
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
https://doi.org/10.1109/LSP.2013.2254712
|
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
https://doi.org/10.1109/TIT.2011.2167214
|
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
https://doi.org/10.1109/TSP.2012.2231076
|
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
https://doi.org/10.1109/TIT.2010.2054653
|
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
https://doi.org/10.1109/TIT.2011.2177632
|
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
https://doi.org/10.1109/TSP.2012.2222377
|
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
https://doi.org/10.1109/TIT.2012.2185923
|
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
https://doi.org/10.1109/TIT.2009.2016006
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|