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

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 {\mathbb{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 \cite{Plan-robust,support} achieved $\Theta ({\delta }^{-2}k\log (n/k))$ and $\tilde{ \Oh} ( \frac{1}{ δ} k \log (n/k))$ measurements, respectively, but the decoding time was $\Omega (nk\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 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,\log n)$ decoding time, which is an exponential improvement over previous work, in terms of the dependence of $n$.