The time-frequency and time-scale communities have recently developed
a large number of overcomplete waveform dictionaries-stationary wavele
ts, wavelet packets, cosine packets, chirplets, and warplets, to name
a few. Decomposition into overcomplete systems is not unique, and seve
ral methods for decomposition have been proposed, including the method
of frames (MOF), Matching pursuit (MP), and, for special dictionaries
, the best orthogonal basis (BOB). Basis Pursuit (BP) is a principle f
or decomposing a signal into an ''optimal'' superposition of dictionar
y elements, where optimal means having the smallest l(1) norm of coeff
icients among all such decompositions. We give examples exhibiting sev
eral advantages over MOF, MP, and BOB, including better sparsity and s
uperresolution. BP has interesting relations to ideas in areas as dive
rse as ill-posed problems, in abstract harmonic analysis, total variat
ion denoising, and multiscale edge denoising. BP in highly overcomplet
e dictionaries leads to large-scale optimization problems. With signal
s of length 8192 and a wavelet packet dictionary, one gets an equivale
nt linear program of size 8192 by 212,992. Such problems can be attack
ed successfully only because of recent advances in linear programming
by interior-point methods. We obtain reasonable success with a primal-
dual logarithmic barrier method and conjugate-gradient solver.