Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0979.94010
Chen, Scott Shaobing; Donoho, David L.; Saunders, Michael A.
Atomic decomposition by basis pursuit. (English)
[J] SIAM Rev. 43, No.1, 129-159 (2001). ISSN 0036-1445; ISSN 1095-7200/e

Summary: The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries---stationary wavelets, wavelet packets, cosine packets, chirplets, and warplets, to name a few. Decomposition into overcomplete systems is not unique, and several methods for decomposition have been proposed, including the method of frames (MOF), matching pursuit (MP), and, for special dictionaries, the best orthogonal basis (BOB).\par Basis pursuit (BP) is a principle for decomposing a signal into an ``optimal'' superposition of dictionary elements, where optimal means having the smallest $l^1$ norm of coefficients among all such decompositions. The authors give examples exhibiting several advantages over MOF, MP, and BOB, including better sparsity and superresolution. BP has interesting relations to ideas in areas as diverse as ill-posed problems, abstract harmonic analysis, total variation denoising, and multiscale edge denoising.\par BP in highly overcomplete dictionaries leads to large-scale optimization problems. With signals of length 8192 and a wavelet packet dictionary, one gets an equivalent linear program of size 8192 by 212,992. Such problems can be attacked successfully only because of recent advances in linear and quadratic programming by interior-point methods. The authors obtain reasonable success with a primal-dual logarithmic barrier method and conjugate-gradient solver.

MSC 2000:: *94A12 Signal theory
65K05 Mathematical programming (numerical methods)
65D15 Algorithms for functional approximation
41A45 Approximation by arbitrary linear expressions

Keywords: overcomplete signal representation; denoising; time-frequency analysis; time-scale analysis; $\ell^1$ norm optimization; matching pursuit; wavelets; wavelet packets; cosine packets; interior-point methods for linear programming; total variation denoising; multiscale edges; MATLAB code

Cited in: Zbl 1069.47025

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]