Examples of basis pursuit

The Time-Frequency and Time-Scale communities have recently developed a large number of overcomplete waveform dictionaries. Decomposition into overcomplete systems is not unique, and several methods for decomposition have been proposed--including the Method of Frames, Matching Pursuit, and, for special dictionaries, the Best Orthogonal Basis. Basis Pursuit is a principle for decomposing a signal into an `optimal' superposition of dictionary elements-- where optimal means having the smallest l¹ norm of coefficients among all such decompositions. We give examples exhibiting several advantages over the Method of Frames, Matching Pursuit and Best Ortho Basis, including better sparsity, and super-resolution. Basis Pursuit in highly overcomplete dictionaries leads to large-scale optimization problems. We obtain reasonable success with a primal-dual logarithmic barrier method and conjugate gradient solver.