Document Open Access Logo

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements

Author Vasileios Nakos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.61.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Vasileios Nakos

Cite As Get BibTex

Vasileios Nakos. On Fast Decoding of High-Dimensional Signals from One-Bit Measurements. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.61

Abstract

In the problem of one-bit compressed sensing, the goal is to find a delta-close estimation of a k-sparse vector x in R^n given the signs of the entries of y = Phi x, where Phi is called the measurement matrix. For the one-bit compressed sensing problem, previous work [Plan, 2013][Gopi, 2013] achieved Theta (delta^{-2} k log(n/k)) and O~( 1/delta k log (n/k)) measurements, respectively, but the decoding time was Omega ( n k log (n/k)). In this paper, using tools and techniques developed in the context of two-stage group testing and streaming algorithms, we contribute towards the direction of sub-linear decoding time. We give a variety of schemes for the different versions of one-bit compressed sensing, such as the for-each and for-all versions, and for support recovery; all these have at most a log k overhead in the number of measurements and poly(k, log n) decoding time, which is an exponential improvement over previous work, in terms of the dependence on n.

Subject Classification

Keywords
  • one-bit compressed sensing
  • sparse recovery
  • heavy hitters
  • dyadic trick
  • combinatorial group testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rudolf Ahlswede, Lars Bäumer, Ning Cai, Harout K. Aydinian, Vladimir Blinovsky, Christian Deppe, and Haik Mashurian, editors. General Theory of Information Transfer and Combinatorics, volume 4123 of Lecture Notes in Computer Science. Springer, 2006. Google Scholar
  2. Richard Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, and Mary Wootters. Exponential decay of reconstruction error from binary measurements of sparse signals. arXiv preprint arXiv:1407.8246, 2014. Google Scholar
  3. Petros Boufounos and Richard G. Baraniuk. 1-bit compressive sensing. In 42nd Annual Conference on Information Sciences and Systems, CISS 2008, Princeton, NJ, USA, 19-21 March 2008, pages 16-21, 2008. URL: http://dx.doi.org/10.1109/CISS.2008.4558487.
  4. E. J. Candes and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? Information Theory, IEEE Transactions on, 52(12):5406-5425, Dec 2006. URL: http://dx.doi.org/10.1109/TIT.2006.885507.
  5. Emmanuel Candes, Mark Rudelson, Terence Tao, and Roman Vershynin. Error correction via linear programming. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 668-681. IEEE, 2005. Google Scholar
  6. Fei-Huang Chang, Huilan Chang, and Frank K. Hwang. Pooling designs for clone library screening in the inhibitor complex model. J. Comb. Optim., 22(2):145-152, 2011. URL: http://dx.doi.org/10.1007/s10878-009-9279-9.
  7. Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002. Google Scholar
  8. Hong-Bin Chen and Frank K. Hwang. A survey on nonadaptive group testing algorithms through the angle of decoding. J. Comb. Optim., 15(1):49-59, 2008. URL: http://dx.doi.org/10.1007/s10878-007-9083-3.
  9. Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159, 2001. Google Scholar
  10. Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005. Google Scholar
  11. Annalisa De Bonis, Leszek Gasieniec, and Ugo Vaccaro. Optimal two-stage algorithms for group testing problems. SIAM Journal on Computing, 34(5):1253-1270, 2005. Google Scholar
  12. David L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1306, 2006. URL: http://dx.doi.org/10.1109/TIT.2006.871582.
  13. Robert Dorfman. The detection of defective members of large populations. Ann. Math. Statist., 14(4):436-440, 12 1943. URL: http://dx.doi.org/10.1214/aoms/1177731363.
  14. Ding-Zhu Du and Frank K. Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 1999. Google Scholar
  15. Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. Approximate sparse recovery: optimizing time and measurements. SIAM Journal on Computing, 41(2):436-453, 2012. Google Scholar
  16. Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. For-all sparse recovery in near-optimal time. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 538-550, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_45.
  17. Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, and Martin J. Strauss. l2/l2-foreach sparse recovery with low risk. In Automata, Languages, and Programming, pages 461-472. Springer, 2013. Google Scholar
  18. Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, and Roman Vershynin. One sketch for all: fast algorithms for compressed sensing. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 237-246. ACM, 2007. Google Scholar
  19. Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya Nori. One-bit compressed sensing: Provable support and vector recovery. In Proceedings of the 30th international conference on machine learning (ICML-13), pages 154-162, 2013. Google Scholar
  20. Vivek K. Goyal, Martin Vetterli, and Nguyen T. Thao. Quantized overcomplete expansions in IR N: analysis, synthesis, and algorithms. Information Theory, IEEE Transactions on, 44(1):16-31, 1998. Google Scholar
  21. C Sinan Güntürk, Mark Lammers, Alex Powell, Rayan Saab, and Özgür Yilmaz. Sigma delta quantization for compressed sensing. In Information Sciences and Systems (CISS), 2010 44th Annual Conference on, pages 1-6. IEEE, 2010. Google Scholar
  22. Ankit Gupta, Robert D. Nowak, and Benjamin Recht. Sample complexity for 1-bit compressed sensing and sparse classification. In ISIT, pages 1553-1557, 2010. Google Scholar
  23. Piotr Indyk, Hung Q. Ngo, and Atri Rudra. Efficiently decodable non-adaptive group testing. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'10, pages 1126-1142, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1873601.1873692.
  24. L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. Information Theory, IEEE Transactions on, 59(4):2082-2102, April 2013. URL: http://dx.doi.org/10.1109/TIT.2012.2234823.
  25. Laurent Jacques, Jason N. Laska, Petros T. Boufounos, and Richard G. Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory, 59(4):2082-2102, 2013. URL: http://dx.doi.org/10.1109/TIT.2012.2234823.
  26. Raghunandan M. Kainkaryam, Angela Bruex, Anna C. Gilbert, John Schiefelbein, and Peter J. Woolf. poolMC: Smart pooling of mRNA samples in microarray experiments. BMC Bioinformatics, 11:299, 2010. URL: http://dx.doi.org/10.1186/1471-2105-11-299.
  27. Felix Krahmer, Rayan Saab, and Özgür Yilmaz. Sigma-delta quantization of sub-gaussian frame expansions and its application to compressed sensing. Information and Inference, page iat007, 2014. Google Scholar
  28. J. N. Laska, Zaiwen Wen, Wotao Yin, and R. G. Baraniuk. Trust, but verify: Fast and accurate signal recovery from 1-bit compressive measurements. Signal Processing, IEEE Transactions on, 59(11):5289-5301, Nov 2011. URL: http://dx.doi.org/10.1109/TSP.2011.2162324.
  29. S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005. URL: http://dx.doi.org/10.1561/0400000002.
  30. Hung Ngo, Ely Porat, and Atri Rudra. Efficiently decodable error-correcting list disjunct matrices and applications. Automata, languages and programming, pages 557-568, 2011. Google Scholar
  31. Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Communications on Pure and Applied Mathematics, 66(8):1275-1297, 2013. Google Scholar
  32. Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. Information Theory, IEEE Transactions on, 59(1):482-494, 2013. Google Scholar
  33. Ely Porat and Martin J. Strauss. Sublinear time, measurement-optimal, sparse recovery for all. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1215-1227. SIAM, 2012. Google Scholar
  34. A. M. Rashad. Random coding bounds on the rate for list-decoding superimposed codes. Problems of Control and Information Theory - Problemy Upravleniya i Teorii Informatsii, 19(2):141-149, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact