In this talk, I will consider an extreme case of compressive sensing, 1-bit compressive sensing, where every measurement is quantised into a single bit, i.e., the sign information of a linear measurement. Due to the 1-bit quantisation, the amplitude information of sparse signals is lost. Surprisingly, only signs of linear measurements might still provide adequate information for a certain level of reconstruction. I will focus on how to reconstruct the support set of a sparse signal from sign measurements in this talk. Firstly, I will show that the 1-bit model with the sign constraint can be formulated equivalently as an 1-bit {$\ell_0$}-minimisation problem with linear equality and inequality constraints. Then, a decoding method, 1-bit basis pursuit, is developed for possibly attacking this 1-bit {$\ell_0$}-minimisation problem. Using the complementary slackness theorem in the Linear Programming, I will derive the nonuniform/uniform support recovery theories through the restricted range space property of the transposed sensing matrix via 1-bit basis pursuit. At last, I will demonstrate the performance of 1-bit basis pursuit in terms of support recovery, approximate sparse recovery and cardinality recovery via some numerical simulations on both Gaussian and Bernoulli matrices. Last updated September 25, 2016, at 12:02 PM |