Statistical mechanics analysis of 1-bit compressed sensing

Lecturer : 
Yinying Xu
Event type: 
HIIT seminar
Event time: 
2015-06-11 13:00 to 14:00
Lecture room T3, Computer Science building, Konemiehentie 2, 02150, Espoo


The 1-bit compressed sensing framework enables the recovery of a sparse vector x from the sign information of each entry of its linear transformation. Discarding the amplitude information can significantly reduce the amount of data, which is highly beneficial in practical applications. We present a L1-norm minimization approach and a Bayesian approach to the signal reconstruction for 1-bit compressed sensing, and analyze their typical performance using statistical mechanics. Utilizing the replica method, we show that the Bayesian approach enables better reconstruction than the l1-norm minimization approach, asymptotically saturating the performance obtained when the non-zero entries positions of the signal are known. We also test a message passing algorithm for signal reconstruction on the basis of belief propagation. The results of numerical experiments are consistent with those of the theoretical analysis.

Speaker Bio:

Yinying Xu is a PhD researcher with professor Yoshiyuki Kabashima at  Department of Computational Intelligence and Systems Science (Interdisciplinary Graduate School of Science and Engineering) at Tokyo Institute of Technology. Kabashima laboratory is interested in broad aspects of "complex systems" in which numerous elements strongly interact with each other. While elucidation of features of such systems is a challenging problem, it can be facilitated by employing statical mechanics apparatus, allowing for tackling mathematical and information processing problems such like optimization problem of a discrete system. Yinying Xu's research interests lie in applying statistical physics methods to problems of compressed sensing and inference with probabilistic graphical models.


Last updated on 4 Jun 2015 by Yi Chen - Page created on 4 Jun 2015 by Yi Chen