CHESS

Thursday, the 21th july in room Chartreuse at 3pm.

Title: "Smoothed L0 (SL0): A fast algorithm for finding the sparse solution of an underdetermined system of linear equations"

Abstract: "In this talk, the problem of finding the sparse solution of an underdetermined systems of linear equations (the "sparse recovery" problem) is considered. We first discuss the significance of this problem by mentioning a few of its applications (including Compressed Sensing), and we point out the uniqueness of such a solution. Then, after pointing out that directly finding such a solution is computationally impossible, we briefly review the main different ideas for finding such a solution, including Matching Pursuit idea and Basis Pursuit idea (minimizing the L1 norm). Finally, we present an approach, called Smoothed L0 (SL0), which tries to directly minimize the L0 norm. We will see that this idea will result in an algorithm which is 2 to 3 orders of magnitude faster than L1-magic (a well-known and fast implementation for Basis Pursuit