×

One-bit compressed sensing by linear programming. (English) Zbl 1335.94018

Summary: We give the first computationally tractable and almost optimal solution to the problem of one-bit compressed sensing, showing how to accurately recover an \(s\)-sparse vector \(x\in \mathbb R^n\) from the signs of \(O(s\log^2(n/s))\) random linear measurements of \(x\). The recovery is achieved by a simple linear program. This result extends to approximately sparse vectors \(x\). Our result is universal in the sense that with high probability, one measurement scheme will successfully recover all sparse vectors simultaneously. The argument is based on solving an equivalent geometric problem on random hyperplane tessellations.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Alon, The probabilistic method (2000) · doi:10.1002/0471722154
[2] Ardestanizadeh, Bit precision analysis for compressed sensing, Proceedings of the 2009 IEEE International Conference on Symposium on Information Theory 1 pp 1–
[3] Bickel, Simultaneous analysis of lasso and Dantzig selector, Ann. Statist. 37 pp 1705– (2009) · Zbl 1173.62022 · doi:10.1214/08-AOS620
[4] Boufounos, Greedy sparse signal reconstruction from sign measurements, 2009 Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers pp 1305–
[5] Boufounos, Reconstruction of sparse signals from distorted randomized measurements, 2010 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) pp 3998–
[6] Boufounos, 42nd Annual Conference on Information Sciences and Systems (CISS) pp 16– (2008) · doi:10.1109/CISS.2008.4558487
[7] Candès, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math. 59 pp 1207– (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[8] Candes, Error correction via linear programming, 46th Annual IEEE Symposium on Foundations of Computer Science pp 668– (2005) · doi:10.1109/SFCS.2005.5464411
[9] Candes, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Transactions on Information Theory 52 pp 5406– (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[10] Candes, The Dantzig selector: statistical estimation when p is much larger than n, Ann. Statist. 35 pp 2313– (2007) · Zbl 1139.62019 · doi:10.1214/009053606000001523
[11] Dai, A comparative study of quantized compressive sensing schemes, IEEE International Symposium on Information Theory, 2009 pp 11–
[12] Damaschke, Threshold group testing, Electronic Notes in Discrete Mathematics 21 pp 265– (2005) · Zbl 1158.68491 · doi:10.1016/j.endm.2005.07.040
[13] Goemans, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach 42 pp 1115– (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[14] Güntürk, Sigma delta quantization for compressed sensing, 2010 44th Annual Conference on Information Sciences and Systems (CISS) pp 1–
[15] Güntürk, Sobolev duals for random frames and sigma-delta quantization of compressed sensing measurements, Preprint (2010)
[16] Gupta, Sample complexity for 1-bit compressed sensing and sparse classification, 2010 IEEE International Symposium on Information Theory Proceedings (ISIT) pp 1553–
[17] Jacques, Dequantizing compressed sensing: when oversampling and non-gaussian constraints combine, IEEE Trans. Inform. Theory 57 pp 559– (2011) · Zbl 1366.94106 · doi:10.1109/TIT.2010.2093310
[18] Jacques , L. Laska , J. N. Boufounos , P. T. Baraniuk , R. G. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors 2011 · Zbl 1364.94130
[19] Laska, Democracy in action: quantization, saturation, and compressive sensing, Appl. Comput. Harmon. Anal. 31 pp 429– (2011) · Zbl 1231.94045 · doi:10.1016/j.acha.2011.02.002
[20] Laska, Trust, but verify: fast and accurate signal recovery from 1-bit compressive measurements, IEEE Trans. Signal Process. 59 pp 11– · Zbl 1393.94314
[21] Mackenzie, Compressed sensing makes every pixel count, What’s Happening in the Mathematical Sciences 7 pp 114– (2009)
[22] Miles, Random points, sets and tessellations on the surface of a sphere, Sankhyā Ser. A 33 pp 145– (1971) · Zbl 0243.60014
[23] Moller, Stochastic geometry and random tessellations, Tessellations in the sciences: virtues, techniques and applications of geometric tilings
[24] Pisier, The volume of convex bodies and Banach space geometry 94 (1989) · Zbl 0698.46008 · doi:10.1017/CBO9780511662454
[25] Sun, Optimal quantization of random measurements in compressed sensing, IEEE International Symposium on Information Theory pp 6– (2009)
[26] Vershynin, Compressed sensing: theory and applications pp 210– (2012) · doi:10.1017/CBO9780511794308.006
[27] Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10 pp 1– (2010) · Zbl 1189.68060 · doi:10.1007/s10208-009-9046-4
[28] Zymnis, Compressed sensing with quantized measurements, IEEE Signal Processing Letters 17 pp 149– (2010) · doi:10.1109/LSP.2009.2035667
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.