2026-07-20T05:27:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7488 2024-03-06T10:40:23Z ddc:004 open_access

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements Nakos, Vasileios one-bit compressed sensing sparse recovery heavy hitters dyadic trick combinatorial group testing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vasileios Nakos 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.61 urn:nbn:de:0030-drops-74887 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.61 eng https://creativecommons.org/licenses/by/3.0/legalcode