Stability of 1-bit compressed sensing in sparse data reconstruction. (English) Zbl 1459.94039
Summary: 1-bit compressing sensing (CS) is an important class of sparse optimization problems. This paper focuses on the stability theory for 1-bit CS with quadratic constraint. The model is rebuilt by reformulating sign measurements by linear equality and inequality constraints, and the quadratic constraint with noise is approximated by polytopes to any level of accuracy. A new concept called restricted weak RSP of a transposed sensing matrix with respect to the measurement vector is introduced. Our results show that this concept is a sufficient and necessary condition for the stability of 1-bit CS without noise and is a sufficient condition if the noise is available.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A20 | Sampling theory in information and communication theory |
| 90C25 | Convex programming |
| 90C90 | Applications of mathematical programming |
Software:
PDCOReferences:
| [1] | Bi, N.; Tan, J., Characterization of ℓ_1 minimizer in one-bit compressed sensing, Analysis and Applications, 17, 6, 1005-1021 (2019) · Zbl 1458.94074 · doi:10.1142/s0219530519500131 |
| [2] | Candes, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/tit.2005.862083 |
| [3] | Candes, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Transactions on Information Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/tit.2006.885507 |
| [4] | Donoho, D. L., Compressed sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/tit.2006.871582 |
| [5] | Tropp, J. A.; Gilbert, A. C., Signal recovery from random measurements via orthogonal matching pursuit, IEEE Transactions on Information Theory, 53, 12, 4655-4666 (2007) · Zbl 1288.94022 · doi:10.1109/tit.2007.909108 |
| [6] | Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Review, 43, 1, 129-159 (2001) · Zbl 0979.94010 · doi:10.1137/s003614450037906x |
| [7] | Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Applied and Computational Harmonic Analysis, 27, 3, 265-274 (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002 |
| [8] | Daubechies, I.; Devore, R.; Fornasier, M.; Güntürk, C. S., Iteratively reweighted least squares minimization for sparse recovery, Communications on Pure and Applied Mathematics, 63, 1, 1-38 (2010) · Zbl 1202.65046 · doi:10.1002/cpa.20303 |
| [9] | Bandeira, A. S.; Dobriban, E.; Mixon, D. G.; Sawin, W. F., Certifying the restricted isometry property is hard, IEEE Transactions on Information Theory, 59, 6, 3448-3450 (2013) · Zbl 1364.94109 · doi:10.1109/tit.2013.2248414 |
| [10] | Baraniuk, R.; Davenport, M.; Devore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constructive Approximation, 28, 3, 253-263 (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x |
| [11] | Emmanuel, J. C., The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathématique, 346, 589-592 (2008) · Zbl 1153.94002 |
| [12] | Emmanuel, J. C.; Eldar, Y. C.; Needell, D.; Randall, P., Compressed sensing with coherent and redundant dictionaries, Applied and Computational Harmonic Analysis, 31, 59-73 (2011) · Zbl 1215.94026 |
| [13] | Gribonval, R.; Nielsen, M., Sparse representations in unions of bases, IEEE Transactions on Information Theory, 49, 12, 3320-3325 (2003) · Zbl 1286.94032 · doi:10.1109/tit.2003.820031 |
| [14] | Yang, C.; Shen, X.; Ma, H.; Gu, Y.; So, H. C., Sparse recovery conditions and performance bounds for ℓ_p-minimization, IEEE Transactions on Signal Processing, 66, 19, 5014-5028 (2018) · Zbl 1414.90294 · doi:10.1109/tsp.2018.2862402 |
| [15] | Zhao, Y.-B., RSP-based analysis for sparsest and least ℓ_1-norm solutions to underdetermined linear systems, IEEE Transactions on Signal Processing, 61, 22, 5777-5788 (2013) · Zbl 1394.94697 · doi:10.1109/tsp.2013.2281030 |
| [16] | Zhao, Y.; Xu, C., 1-Bit compressive sensing: reformulation and RRSP-based sign recovery theory, Science China Mathematics, 59, 10, 2049-2074 (2016) · Zbl 1349.90617 · doi:10.1007/s11425-016-5153-2 |
| [17] | Liu, J.; Jin, J.; Gu, Y., Robustness of sparse recovery via, IEEE Transactions on Information Theory, 61, 7, 3996-4014 (2015) · Zbl 1359.94126 · doi:10.1109/tit.2015.2438302 |
| [18] | Yang, C. Z.; Shen, X. Y.; Ma, H. B.; Chen, B. D.; Gu, Y. T.; So, H. C., Weakly convex regularized robust sparse recovery methods with theoretical guarantees, IEEE Transactions on Signal Processing, 67, 19, 5046-5061 (2019) · Zbl 07123415 · doi:10.1109/tsp.2019.2935906 |
| [19] | Kueng, R.; Jung, P., Robust nonnegative sparse recovery and the nullspace property of 0/1 measurements, IEEE Transactions on Information Theory, 64, 689-703 (2018) · Zbl 1390.94254 · doi:10.1109/tit.2017.2746620 |
| [20] | Boufounos, P. T.; Baraniuk, R. G., 1-bit compressive sensing, Proceedings of the 2008 42nd Annual Conference on Information Sciences and Systems, IEEE |
| [21] | Ayaz, U.; Dirksen, S.; Rauhut, H., Uniform recovery of fusion frame structured sparse signals, Applied and Computational Harmonic Analysis, 41, 341-361 (2014) · Zbl 1360.94061 |
| [22] | Saab, R.; Wang, R.; Yilmaz, O., Quantization of compressive samples with stable and robust recovery, Applied and Computational Harmonic Analysis, 44, 123-143 (2018) · Zbl 1375.94079 · doi:10.1016/j.acha.2016.04.005 |
| [23] | Sun, Q., Recovery of sparsest signals via \(l_q\)-minimization, Applied and Computational Harmonic Analysis, 32, 329-341 (2012) · Zbl 1266.94017 |
| [24] | Xu, J. L.; Zhao, Y. B., Stability analysis for a class of sparse optimization problems, Optimization Methods and Software, 35, 836-854 (2020) · Zbl 1454.90026 · doi:10.1080/10556788.2020.1734003 |
| [25] | Zhao, Y. B., Sparse Optimization Theory and Methods (2018), Boca Raton, FL, USA: CRC Press, Taylor, Francis Group, Boca Raton, FL, USA · Zbl 1391.90003 |
| [26] | Zhao, Y. B.; Jiang, H. Y.; Luo, Z. Q., Weak stability of \(l_1\)-minimization methods in sparse data reconstruction, Mathematics of Operations Research, 44, 173-195 (2019) · Zbl 1441.90091 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
