  One-bit compressed sensing (1bCS) is an extremely quantized signal
acquisition method that has been proposed and studied rigorously in the past
decade. In 1bCS, linear samples of a high dimensional signal are quantized to
only one bit per sample (sign of the measurement). Assuming the original signal
vector to be sparse, existing results in 1bCS either aim to find the support of
the vector, or approximate the signal allowing a small error. The focus of this
paper is support recovery, which often also computationally facilitate
approximate signal recovery. A {\em universal} measurement matrix for 1bCS
refers to one set of measurements that work for all sparse signals. With
universality, it is known that $\tilde{\Theta}(k^2)$ 1bCS measurements are
necessary and sufficient for support recovery (where $k$ denotes the sparsity).
To improve the dependence on sparsity from quadratic to linear, in this work we
propose approximate support recovery (allowing $\epsilon>0$ proportion of
errors), and superset recovery (allowing $\epsilon$ proportion of false
positives). We show that the first type of recovery is possible with
$\tilde{O}(k/\epsilon)$ measurements, while the later type of recovery, more
challenging, is possible with $\tilde{O}(\max\{k/\epsilon,k^{3/2}\})$
measurements. We also show that in both cases $\Omega(k/\epsilon)$ measurements
would be necessary for universal recovery.
  Improved results are possible if we consider universal recovery within a
restricted class of signals, such as rational signals, or signals with bounded
dynamic range. In both cases superset recovery is possible with only
$\tilde{O}(k/\epsilon)$ measurements. Other results on universal but
approximate support recovery are also provided in this paper. All of our main
recovery algorithms are simple and polynomial-time.
