ICTEAM > ELEN > ISPGroup > ISPS > Calendar > ABS280916


Title: "Restricted Range Space Property Based Theory for 1-Bit Compressive Sensing"

Speaker: Chunlei Xu

Location: "Shannon" Seminar Room, Place du Levant 3, Maxwell Building, 1st floor

Date / Time (duration): Wednesday 28/09/2016, 11h00 (~45')

Abstract: Plenty works have been devoted to the study of compressive sensing over the past decades. Such a promising development of compressive sensing has a great impact on many aspects of signal and image processing. One of the key mathematical problems addressed in compressive sensing is how to reconstruct a sparse signal from linear/nonlinear measurements via a decoding algorithm. In the classic compressive sensing, it is well known that to exactly reconstruct the sparsest signal from a limited number of linear measurements is possible when the sensing matrix admits certain properties.

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