Sparse Representations and the Basis Pursuit Algorithm
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 searching such representation becomes a hard to solve 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. 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 then turn to extend previous results for arbitrary
dictionaries, showing that all previous work falls as a special case of
the new theory. Finally, we show work in progress that extends the above
results for relaxed sparsity definition, via the use of L_p norm where
0