  Is it possible to obliviously construct a set of hyperplanes H such that you
can approximate a unit vector x when you are given the side on which the vector
lies with respect to every h in H? In the sparse recovery literature, where x
is approximately k-sparse, this problem is called one-bit compressed sensing
and has received a fair amount of attention the last decade. In this paper we
obtain the first scheme that achieves almost optimal measurements and sublinear
decoding time for one-bit compressed sensing in the non-uniform case. For a
large range of parameters, we improve the state of the art in both the number
of measurements and the decoding time.
