TITLE: Sparse Representations and the Basis Pursuit Algorithm
SPEAKER: Michael Elad [Stanford University)
Contact information:
The Computer Science Department (SCCM)
Stanford University
Gates 2B, Room 282, Stanford 90305-9025, CA. USA.
Phone: (650)-723-7685
email: elad@sccm.stanford.edu
Website: http://www-sccm.stanford.edu/~elad
DATE: 2:00-3:00 P.M., Thursday, April 24, 2003
LOCATION: Sigma, 1L (PA)
HOST: Vinay Deolalikar
ABSTRACT:
Overcomplete transforms are appealing due to their ability to cover a
diversity of signal behaviors while using sparse representations. However,
finding such representations requires the solution of a non-convex and
highly non-smooth optimization problem. The "Basis-Pursuit" (BP)
algorithm (Chen, Donoho, and Saunders - 1995) is a stable approximate solver for the
above task, replacing the non-convex L^0 minimization with a L^1 norm. BP is
also known to be suited for the denoising task, with parallel and even
better results, when compared to leading methods such as Wavelet denoising,
Total-Variation (TV), and more.
In this talk we discuss the BP behavior, conditions for its success, and its
relation to competing algorithms. Referring to the BP as a transform
algorithm, we show theoretical results that indeed assures the BP optimality
for sparse enough representations. We then turn to discuss the denoising
application and show that the BP can be interpreted as a Bayesian approach
for the inverse problem of signal estimation under noise, with pre-specified
prior. We show how known noise removal algorithms such as the TV, (shift
invariant) Wavelet denoising, and Bilateral filter, are all essentially BP
methods with different choice of a dictionary.
* Joint work with A.M. Bruckstein - CS department, Technion, Israel, D.L.
Donoho - Statistics, Stanford, CA, and P. Milanfar, UC Santa Cruz, CA.
|
|
|
printable version
