Transforming a signal is typically done in order to simplify its representation. Among the many ways to represent signals, the use of a linear combination taken from an over-complete dictionary is appealing due to its ability to cover a diversity of signal behaviors in one transform. However, with this benefit comes the problem of non-unique representation. Choosing the sparsest of all representations aligns well with our desire for simple signal description, but the search for such representation translates into a very hard non-convex and highly non-smooth optimization task. The "Basis-Pursuit" (BP) algorithm (Chen, Donoho, and Saunders - 1995) is a stable approximate solver for the above task, that replaces the non-convex L_0 minimization by an L_1 norm. A later work by Donoho and Huo (1998) theoretically proved that for specific dictionaries built from pair of ortho-bases and for sparse enough representations, the BP algorithm is indeed optimal.

In this talk we start by describing Donoho and Huo's work on the BP algorithm, and then show how these results could be further improved. We first discuss the case of pair of ortho-bases and show tighter bounds on the required sparsity of the signal representation that guarantees BP-optimality. We than turn to extend previous results for arbitrary dictionaries, showing that all previous work falls a special case of the new theory. Finally, we discuss denoising of signals based on the BP and show its close relation to Bayesian theory in general, and the bilateral filter in particular.

Joint work with A.M. Bruckstein (Technion), D.L. Donoho (Stanford).