Information and System Group

January 2013

No Date Title Speaker Presentation Discussion
1 2013-01-10  Statistical physics-based re construction in compressed sensing Jaewook Kang (pdf)
In this report, the author introduces a expectation maximization (EM) based belief propagation algorithm (BP) for sparse recovery, named EM-BP. The algorithm have been mainly devised by Krzakala et al. from ParisTech in France. The properties of EM-BP are as given below:1) It is A low-computation approach to sparse recovery,

2) It works well without the prior knowledge of the signal,

3) It overcomes the l1 phase transition given by Donoho and Tanner  under the noiseless setup,

4) It is further improved in conjunction with seeding matrices (or spatial coupling matrices).

The main purpose of this report regenerates a precise description of EM-BP derivation from the reference paper. It might be very helpful for understanding of EM-BP algorithm, and an answer for such a question: How and why does the algorithm work ? Therefore, we will focus on the explanation of 1) and 2) in the properties, and just show the result of the paper with respect to that of 3) and 4).

2 2013-01-24 A fast approach for over-complete sparse decomposition based on smoothed L0 norm Oliver   (PDF)  (PDF)
This paper proposes a fast algorithm for overcomplete sparse decomposition.The algorithm is derived by directly minimizing the L0 norm after smoothening. Hence, the algorithm is named as smoothed L0 (SL0) algorithm.  The authors demonstrate that their algorithm is 2-3 orders of magnitude faster than the state-of-the-art interior point solvers with same (or better) accuracy.