One Bit Support Recovery

The theory of Compressed Sensing (CS) enables reconstruction of sparse or compressible signals from a small number of linear measurements, relative to the dimension of the signal space. Rather than the uniformly sampling, the compressive sensing computes inner products with a randomized dictionary of test functions. The signal is then recovered by a convex optimization. One of the main challenges in CS is to find the support of a sparse signal from a set of observations. In this paper we consider the case of 1-bit measurements, which preserve only the sign information of the random measurements. Although it is possible to recover using the classical compressive sensing approach or fixed point continuation (FPC) algorithm by treating the 1-bit measurements as ±1 measurement values, in this paper we reformulate the problem to a convex problem and use a search algorithm to recover the support. The simulation results demonstrate that the percentage of the support of a sparse signal exactly recovered by our method is significantly better than the classical compressive sensing reconstruction methods and the FPC algorithm.