The time-frequency and time-scale communities have recently developed a lar
ge number of overcomplete waveform dictionaries-stationary wavelets, wavele
t packets, cosine packets, chirplets, and warplets, to name a few. Decompos
ition into overcomplete systems is not unique, and several methods for deco
mposition have been proposed, including the method of frames (MOF), matchin
g pursuit (MP), and, for special dictionaries, the best orthogonal basis (B
OB).
Basis pursuit (BP) is a principle for decomposing a signal into an "optimal
" superposition of dictionary elements, where optimal means having the smal
lest l(1) norm of coefficients among all such decompositions. We give examp
les exhibiting several advantages over MOF, MP, and BOB, including better s
parsity and superresolution. BP has interesting relations to ideas in areas
as diverse as ill-posed problems, abstract harmonic analysis, total variat
ion denoising, and multiscale edge denoising.
BP in highly overcomplete dictionaries leads to large-scale optimization pr
oblems. With signals of length 8192 and a wavelet packet dictionary one get
s an equivalent linear program of size 8192 by 212,992. Such problems can b
e attacked successfully only because of recent advances in linear and quadr
atic programming by interior-point methods. We obtain reasonable success wi
th a primal-dual logarithmic barrier method and conjugate-gradient solver.