The Weizmann Institute of Science Faculty of Mathematics and Computer Science Vision and Robotics Seminar Dr. Michael Elad Stanford University will speak on On sparse representations and the basis pursuit algorithm Abstract: The Basis Pursuit (BP) algorithm was proposed by Chen, Donoho and Saunders in 1995. This algorithm is a numerically solvable method for finding sparse representations and denoising of signals. In this talk we shall review the BP and then discuss its analysis. The talk will focus both on the BP as a transform tool for over-complete dictionaries, and also as a non-linear filter. Referring to the transform interpretation, we show that although considered to be an approximate convex programming solution to an original combinatorial problem, the BP actually succeeds in finding the sparsest of all representations under some conditions. We show the analysis that leads to these conditions and discuss their implications. When regarded as a non-linear filter, an intriguing question is what role should the choice of the dictionary play in the success of the denoising algorithm, and what is the importance of over-completeness. We show that the BP has a Bayesian interpretation, and the choice of the dictionary is dual to the problem of defining the Prior operator. Specifically, we show that total variation filtering, Wave let denoising, the bilateral filter, and shift-invariant wavelet denoising, are all special cases of the BP for specific choice of dictionaries. * Joint work with David Donoho - Statistics - Stanford, and Peyman Milanfar - UC- Santa-Cruz (currently on sabbatical at Stanford). The lecture will take place in the Lecture Hall, Room 1, Ziskind Building on Wednesday, November 27, 2002 at 16:00 Please note the change in day and time