{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T19:06:32Z","timestamp":1778267192397,"version":"3.51.4"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T00:00:00Z","timestamp":1728518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["2133484, 2127929"],"award-info":[{"award-number":["2133484, 2127929"]}]},{"name":"NSF GRFP","award":["DGE-2038238"],"award-info":[{"award-number":["DGE-2038238"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>\n            <jats:italic>Compressed sensing<\/jats:italic>\n            has been a very successful high-dimensional signal acquisition and recovery technique that relies on linear operations. However, the actual measurements of signals have to be quantized before storing or processing them. One-bit compressed sensing is a heavily quantized version of compressed sensing, where each linear measurement of a signal is reduced to just one bit: the sign of the measurement. Once enough of such measurements are collected, the recovery problem in one-bit compressed sensing aims to find the original signal with as much accuracy as possible. The recovery problem is related to the traditional \u201chalfspace-learning\u201d problem in learning theory.\n          <\/jats:p>\n          <jats:p>\n            \u00a0\u00a0 For recovery of sparse vectors, a popular reconstruction method from one-bit measurements is the\n            <jats:italic>binary iterative hard thresholding (BIHT)<\/jats:italic>\n            algorithm. The algorithm is a simple projected subgradient descent method and is known to converge well empirically, despite the nonconvexity of the problem. The convergence property of BIHT was not theoretically fully justified (e.g., it is known that a number of measurement greater than\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\max \\lbrace k^{10}, 24^{48}, k^{3.5}\/\\epsilon \\rbrace\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , where\n            <jats:italic>k<\/jats:italic>\n            is the sparsity and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            denotes the approximation error, is sufficient, Friedlander et\u00a0al. [2021]. In this article we show that the BIHT estimates converge to the original signal with only\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{k}{\\epsilon }\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            measurements (up to logarithmic factors). Note that, this dependence on\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is optimal for any recovery method in one-bit compressed sensing. With this result, to the best of our knowledge, BIHT is the only practical and efficient (polynomial time) algorithm that requires the optimal number of measurements in all parameters (both\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem under suitable structural conditions.\n          <\/jats:p>","DOI":"10.1145\/3680542","type":"journal-article","created":{"date-parts":[[2024,7,29]],"date-time":"2024-07-29T11:09:33Z","timestamp":1722251373000},"page":"1-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8777-4233","authenticated-orcid":false,"given":"Namiko","family":"Matsumoto","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, University of California San Diego, La Jolla, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4605-7996","authenticated-orcid":false,"given":"Arya","family":"Mazumdar","sequence":"additional","affiliation":[{"name":"Halicioglu Data Science Institute, University of California San Diego, La Jolla, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,10,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006950"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2688381"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2008.4558487"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_3_8_2","first-page":"10387","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems (NeurIPS\u201919)","author":"Flodin Larkin","year":"2019","unstructured":"Larkin Flodin, Venkata Gandikota, and Arya Mazumdar. 2019. Superset technique for approximate recovery in one-bit compressed sensing. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems (NeurIPS\u201919), Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). Curran Associates, Inc., 10387\u201310396."},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/978-3-319-59912-0_4","volume-title":"Approximation Theory XV: San Antonio 2016 15","author":"Foucart Simon","year":"2017","unstructured":"Simon Foucart. 2017. Flavors of compressive sensing. In Approximation Theory XV: San Antonio 2016 15. Springer, Berlin, 61\u2013104."},{"issue":"2","key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1109\/TIT.2021.3124598","article-title":"NBIHT: An efficient algorithm for 1-bit compressed sensing with optimal error decay rate","volume":"68","author":"Friedlander Michael P.","year":"2021","unstructured":"Michael P. Friedlander, Halyun Jeong, Yaniv Plan, and \u00d6zg\u00fcr Y\u0131lmaz. 2021. NBIHT: An efficient algorithm for 1-bit compressed sensing with optimal error decay rate. IEEE Trans. Inf. Theory 68, 2 (2021), 1157\u20131177.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_3_3_11_2","series-title":"JMLR Workshop and Conference Proceedings","first-page":"154","volume-title":"Proceedings of the 30th International Conference on Machine Learning (ICML\u201913),","volume":"28","author":"Gopi Sivakant","year":"2013","unstructured":"Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya Nori. 2013. One-bit compressed sensing: Provable support and vector recovery. In Proceedings of the 30th International Conference on Machine Learning (ICML\u201913),JMLR Workshop and Conference Proceedings, Vol. 28. JMLR.org, 154\u2013162."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2011.5766202"},{"key":"e_1_3_3_13_2","unstructured":"Laurent Jacques K\u00e9vin Degraux and Christophe De Vleeschouwer. 2013. Quantized iterative hard thresholding: Bridging 1-bit and high-resolution quantized compressed sensing. arXiv:1305.1786. Retrieved from http:\/\/arxiv.org\/abs\/1305.1786"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2234823"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2527637"},{"key":"e_1_3_3_16_2","series-title":"JMLR Workshop and Conference Proceedings","first-page":"1515","volume-title":"Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS\u201916),","volume":"51","author":"Li Ping","year":"2016","unstructured":"Ping Li. 2016. One scan 1-bit compressed sensing. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS\u201916),JMLR Workshop and Conference Proceedings, Arthur Gretton and Christian C. Robert (Eds.), Vol. 51. JMLR.org, 1515\u20131523."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2922328"},{"key":"e_1_3_3_18_2","first-page":"106:1\u2013106:20","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922) (LIPIcs)","volume":"215","author":"Mazumdar Arya","year":"2022","unstructured":"Arya Mazumdar and Soumyabrata Pal. 2022. Support recovery in universal one-bit compressed sensing. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922) (LIPIcs), Mark Braverman (Ed.), Vol. 215. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 106:1\u2013106:20."},{"key":"e_1_3_3_19_2","unstructured":"Samet Oymak and Ben Recht. 2015. Near-optimal bounds for binary embeddings of arbitrary sets. arXiv:1512.04433. Retrieved from http:\/\/arxiv.org\/abs\/1512.04433"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2207945"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21442"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2207945"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2517008"},{"issue":"1","key":"e_1_3_3_24_2","first-page":"1","article-title":"High-dimensional estimation with geometric constraints","volume":"6","author":"Plan Yaniv","year":"2017","unstructured":"Yaniv Plan, Roman Vershynin, and Elena Yudovina. 2017. High-dimensional estimation with geometric constraints. Inf. Inference: J. IMA 6, 1 (2017), 1\u201340.","journal-title":"Inf. Inference: J. IMA"},{"issue":"1","key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.acha.2016.04.005","article-title":"Quantization of compressive samples with stable and robust recovery","volume":"44","author":"Saab Rayan","year":"2018","unstructured":"Rayan Saab, Rongrong Wang, and \u00d6zg\u00fcr Y\u0131lmaz. 2018. Quantization of compressive samples with stable and robust recovery. Appl. Comput. Harmon. Anal. 44, 1 (2018), 123\u2013143.","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3680542","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3680542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:11Z","timestamp":1750295891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3680542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,10]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3680542"],"URL":"https:\/\/doi.org\/10.1145\/3680542","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,10]]},"assertion":[{"value":"2022-09-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}