On fast decoding of high-dimensional signals from one-bit measurements

DOI10.4230/LIPICS.ICALP.2017.61zbMATH Open1457.94047arXiv1603.08585MaRDI QIDQ5111392FDOQ5111392

Authors: Vasileios Nakos 

Publication date: 27 May 2020

Abstract: In the problem of one-bit compressed sensing, the goal is to find a $delta$-close estimation of a $k$-sparse vector $xinmathbb{R}^n$ given the signs of the entries of $y=Phix$, where $Phi$ is called the measurement matrix. For the one-bit compressed sensing problem, previous work cite{Plan-robust,support} achieved $Theta(delt{a}^{-2}klog(n/k))$ and $ildeOh(frac1deltaklog(n/k))$ measurements, respectively, but the decoding time was $Omega(nklog(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 very fast 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 version, support recovery; all these have $poly(k,logn)$ decoding time, which is an exponential improvement over previous work, in terms of the dependence of $n$.

Full work available at URL: https://arxiv.org/abs/1603.08585

Recommendations

• One-bit compressed sensing by linear programming
• One-bit compressive sensing of dictionary-sparse signals
• One-bit compressed sensing with non-Gaussian measurements
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• Sublinear time, measurement-optimal, sparse recovery for all

zbMATH Keywords

sparse recoveryheavy hitterscombinatorial group testingone-bit compressed sensingdyadic trick

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Randomized algorithms (68W20)

Cited In (2)

• A Further Result on the ICA One-Bit-Matching Conjecture
• One-bit compressed sensing by linear programming

This page was built for publication: On fast decoding of high-dimensional signals from one-bit measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111392)