×

One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method. (English) Zbl 1468.94130

Summary: One-bit compressed sensing aims to recover unknown sparse signals from extremely quantized linear measurements which just capture their signs. In this paper, we propose a nonconvex \(\ell_p\) \((0<p<1)\) minimization model for one-bit compressed sensing problem and define the set of \(\ell_p\) effectively \(s\)-sparse signals which contains genuinely \(s\)-sparse signals. Utilizing properties of covering number, we show that our method can recover the direction of \(\ell_p\) effectively \(s\)-sparse signals with error order \(\mathcal{O}((s/m\log(mn/s))^{\frac{2-p}{2+p}})\). We also employ thresholded one-bit measurements to estimate the magnitude of signals and prove that any \(\ell_p\) effectively \(s\)-sparse bounded signal \(\mathfrak{x}\) can be estimated using augmented \(\ell_p\) minimization model and empirical distribution function method respectively. Especially, to recover \(\ell_p\) effectively \(s\)-sparse signals in practice, we introduce an adaptive binary iterative thresholding algorithm which can be utilized without knowing the sparsity of underlying signals. Numerical experiments on both synthetic and real-world data sets are conducted to demonstrate the superiority of our algorithm.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods

Software:

Daisy
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Donoho D L 2006 Compressed sensing IEEE Trans. Inf. Theory52 1289-306 · Zbl 1288.94016 · doi:10.1109/tit.2006.871582
[2] Zhang N and Li Q 2017 On optimal solutions of the constrained ℓ0 regularization and its penalty problem Inverse Problems33 025010 · Zbl 1360.65183 · doi:10.1088/1361-6420/33/2/025010
[3] Wen J M, Li D F and Zhu F M 2015 Stable recovery of sparse signals via ℓp-minimization Appl. Comput. Harmon. Anal.38 161-76 · Zbl 1345.94020 · doi:10.1016/j.acha.2014.06.003
[4] Chen W G and Li Y L 2019 Recovery of signals under the condition on RIC and ROC via prior support information Appl. Comput. Harmon. Anal.46 417-30 · Zbl 1405.94023 · doi:10.1016/j.acha.2018.02.003
[5] Mo Q and Li S 2011 New bounds on the restricted isometry constant δ2k Appl. Comput. Harmon. Anal.31 460-8 · Zbl 1231.94027 · doi:10.1016/j.acha.2011.04.005
[6] Wang J J, Zhang F, Huang J W and Yuan C A 2019 A nonconvex penalty function with integral convolution approximation for compressed sensing Signal Process.158 116-28 · doi:10.1016/j.sigpro.2019.01.001
[7] Candés E J and Tao T 2006 Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory52 5406-25 · Zbl 1309.94033 · doi:10.1109/tit.2006.885507
[8] Lu J, Qiao K, Li X R, Lu Z S and Zhao Y R 2019 ℓ0-minimization methods for image restoration problems based on wavelet frames Inverse Problems35 064001 · Zbl 1448.94024 · doi:10.1088/1361-6420/ab08de
[9] Candés E J, Romberg J and Tao T 2006 Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information IEEE Trans. Inf. Theory52 489-509 · Zbl 1231.94017 · doi:10.1109/tit.2005.862083
[10] Donoho D L, Elad M and Temlyakov V N 2006 Stable recovery of sparse overcomplete respresentations in the presence of noise IEEE Trans. Inf. Theory52 6-18 · Zbl 1288.94017 · doi:10.1109/tit.2005.860430
[11] Candes E J, Wakin M B and Boyd S P 2008 Enhancing sparsity by reweighted ℓ1 minimization J. Fourier Anal. Appl.14 877-905 · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x
[12] Chartrand R 2007 Exact reconstruction of sparse signals via nonconvex minimization IEEE Signal Process. Lett.14 707-10 · doi:10.1109/lsp.2007.898300
[13] Chartrand R and Staneva V 2008 Restricted isometry properties and nonconvex compressive sensing Inverse Problems24 035020 · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[14] Xu Z B, Chang X Y, Xu F M and Zhang H 2012 L1/2 regularization: a thresholding representation theory and a fast solver IEEE Transactions on Neural Networks and Learning Systems23 1013-27 · doi:10.1109/tnnls.2012.2197412
[15] Cui A G, Peng J G, Li H Y, Wen M and Jia J X 2018 Iterative thresholding algorithm based on non-convex method for modified ℓp-norm regularization minimization J. Comput. Appl. Math.347 137-80 · Zbl 1410.90162 · doi:10.1016/j.cam.2018.08.021
[16] Zeng J S, Lin S B, Wang Y and Xu Z B 2014 L1/2 regularization: convergence of iterative half thresholding algorithm IEEE Trans. Signal Process.62 2317-29 · Zbl 1393.90145 · doi:10.1109/tsp.2014.2309076
[17] Stojnic M, Xu W and Hassibi B 2008 Compressed sensing-probabilistic analysis of a null-space characterization 2008 IEEE Int. Conf. on Acoustics, Speech and Signal Processing pp 3377-80 · doi:10.1109/ICASSP.2008.4518375
[18] Khajehnejad M A, Dimakis A G, Xu W and Hassibi B 2011 Sparse recovery of nonnegative signals with minimal expansion IEEE Trans. Signal Process.59 196-208 · Zbl 1392.94272 · doi:10.1109/tsp.2010.2082536
[19] Ge H M, Wen J M and Chen W G 2018 The null space property of the truncated ℓ1−2-minimization IEEE Signal Process. Lett.25 1261-65 · doi:10.1109/lsp.2018.2852138
[20] Woodworth J and Chartrand R 2016 Compressed sensing recovery via nonconvex shrinkage penalties Inverse Problems32 075004 · Zbl 1347.65111 · doi:10.1088/0266-5611/32/7/075004
[21] Ge H, Wang L, Wen J M and Xian J 2019 A RIP condition for exact support recovery with covariance-assisted matching pursuit IEEE Signal Process. Lett.26 520-4 · doi:10.1109/lsp.2019.2896543
[22] Wang Y, Wang J J and Xu Z B 2014 Restricted p-isometry properties of nonconvex block-sparse compressed sensing Signal Process.104 188-96 · doi:10.1016/j.sigpro.2014.03.040
[23] Wang J J, Huang J W, Zhang F and Wang W D 2019 Group sparse recovery in impulsive noise via alternating direction method of multipliers Appl. Comput. Harmon. Anal. (accepted) (http://dx.doi.org/10.1016/j.acha.2019.04.002) · Zbl 1458.94139 · doi:10.1016/j.acha.2019.04.002
[24] Wu R and Chen D R 2013 The improved bounds of restricted isometry constant for recovery via ℓp-minimization IEEE Trans. Inf. Theory59 6142-47 · Zbl 1364.94177 · doi:10.1109/tit.2013.2262495
[25] Cai T T, Wang L and Xu G W 2010 Shifting inequality and recovery of sparse signals IEEE Trans. Signal Process.58 1300-08 · Zbl 1392.94117 · doi:10.1109/tsp.2009.2034936
[26] Calderbank R, Thompson A and Xie Y 2015 On block coherence of frames Appl. Comput. Harmon. Anal.38 50-71 · Zbl 1302.65097 · doi:10.1016/j.acha.2014.03.003
[27] Foucart S and Rauhut H 2013 A Mathematical Introduction to Compressive Sensing (Cambridge, MA: Birkhäuser) · Zbl 1315.94002 · doi:10.1007/978-0-8176-4948-7
[28] Le B, Rondeau T W, Reed J H and Bostian C W 2005 Analog-to-digital converters IEEE Signal Process. Mag.22 69-77 · doi:10.1109/msp.2005.1550190
[29] Boufounos P T and Baraniuk R G 2008 1-bit compressive sensing 42nd Annual Conf. on Information Sciences and Systems pp 16-21
[30] Jacques L, Laska J N, Boufounos P T and Baraniuk R G 2013 Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors IEEE Trans. Inf. Theory59 2082-102 · Zbl 1364.94130 · doi:10.1109/tit.2012.2234823
[31] Plan Y and Vershynin R 2013 One-bit compressed sensing by linear programming Commun. Pure Appl. Math.66 1275-97 · Zbl 1335.94018 · doi:10.1002/cpa.21442
[32] Plan Y and Vershynin R 2013 Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach IEEE Trans. Inf. Theory59 482-94 · Zbl 1364.94153 · doi:10.1109/tit.2012.2207945
[33] Yan M, Yang Y and Osher S 2012 Robust 1-bit compressive sensing using adaptive outlier pursuit IEEE Trans. Signal Process.60 3868-75 · Zbl 1393.94723 · doi:10.1109/tsp.2012.2193397
[34] Ai A, Lapanowski A, Plan Y and Vershynin R 2014 One-bit compressed sensing with non-Gaussian measurements Linear Algebr. Appl.441 222-39 · Zbl 1332.94041 · doi:10.1016/j.laa.2013.04.002
[35] Dai D Q, Shen L X, Xu Y S and Zhang N 2016 Noisy 1-bit compressive sensing: models and algorithms Appl. Comput. Harmon. Anal.40 1-32 · Zbl 1331.65085 · doi:10.1016/j.acha.2014.12.001
[36] Knudson K, Saab R and Ward R 2016 One-bit compressive sensing with norm estimation IEEE Trans. Inf. Theory62 2748-58 · Zbl 1359.94117 · doi:10.1109/tit.2016.2527637
[37] Baraniuk R, Foucart S, Needell D, Plan Y and Wootters M 2017 Exponential decay of reconstruction error from binary measurements of sparse signals IEEE Trans. Inf. Theory63 3368-85 · doi:10.1109/tit.2017.2688381
[38] Baraniuk R, Foucart S, Needell D, Plan Y and Wootters M 2017 One-bit compressive sensing of dictionary-sparse signals Information and Inference: A Journal of the IMA7 83-104 · Zbl 1446.94017 · doi:10.1093/imaiai/iax009
[39] Lopes M 2013 Estimating unknown sparsity in compressed sensing Int. Conf. on Machine Learning pp 217-25
[40] Lopes M 2016 Unknown sparsity in compressed sensing: denoising and inference IEEE Trans. Inf. Theory62 5145-66 · Zbl 1359.94130 · doi:10.1109/tit.2016.2587772
[41] Roman V 2018 High-dimensional Probability: An Introduction with Applications in Data Science vol 47 (Cambridge: Cambridge University Press) · Zbl 1430.60005
[42] Plan Y and Vershynin R 2014 Dimension reduction by random hyperplane tessellations Discrete and Computational Geometry51 438-61 · Zbl 1296.52014 · doi:10.1007/s00454-013-9561-6
[43] Chandrasekaran V, Recht B, Parrilo P A and Willsky A S 2012 The convex geometry of linear inverse problems Found. Comput. Math.12 805-49 · Zbl 1280.52008 · doi:10.1007/s10208-012-9135-7
[44] Bilyk D and Lacey M T 2015 Random tessellations, restricted isometric embeddings, and one bit sensing arXiv:1512.06697
[45] Ball K 1997 An elementary introduction to modern convex geometry Flavors of Geometry vol 31 (Cambridge, U.K.: CambridgeUniversity Press) pp 1-58 · Zbl 0901.52002
[46] Bredies K, Lorenz D A and Reiterer S 2015 Minimization of non-smooth, non-convex functionals by iterative thresholding J. Optim. Theory Appl.165 78-112 · Zbl 1321.49048 · doi:10.1007/s10957-014-0614-7
[47] Moor B D 2011 DaISy: Database for the Identification of Systems
[48] Dvoretzky A, Kiefer J and Wolfowitz J 1956 Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator Ann. Inst. Stat. Math.27 642-69 · Zbl 0073.14603 · doi:10.1214/aoms/1177728174
[49] Ledoux M and Talagrand M 1991 Probability in Banach Spaces: Isoperimetry and Processes (Berlin: Springer) · Zbl 0748.60004 · doi:10.1007/978-3-642-20212-4
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.