Atomic Decomposition by Basis Pursuit

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