Atomic decomposition by basis pursuit
Atomic decomposition by basis pursuit
复制标题
DOI：
10.1137/s003614450037906x
复制
发表时间：
2001-03-01
期刊：
影响因子：
10.2
通讯作者：
Saunders, MA
中科院分区：
文献类型：
--
作者：
Chen, SSB;Donoho, DL;Saunders, MA
时间频率和时间尺度社区最近开发了大量的过完备的波形字典-静止小波，小波包，余弦包，小波和小波，仅举几例。分解成过完备系统并不是唯一的，已经提出了几种分解方法，包括帧法（MOF）、匹配追踪法（MP）以及对于特殊字典的最佳正交基法（BOB）。基追求（BP）是一种将信号分解为字典元素的“最优”叠加的原理，其中最优意味着在所有这些分解中具有最小的l(1)范数系数。我们给出的例子显示了与MOF、MP和BOB相比的几个优点，包括更好的稀疏性和超分辨率。BP与不适定问题、抽象谐波分析、全变差去噪和多尺度边缘去噪等领域的思想有着有趣的关系。高度过完备字典中的BP会导致大规模的优化问题。使用长度为8192的信号和一个小波包字典，可以得到大小为8192 × 212992的等效线性程序。由于线性规划和二次规划的内点法的最新进展，这类问题可以成功地解决。我们用原始-对偶对数势垒法和共轭梯度解算器取得了一定的成功。
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).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. We 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.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. We obtain reasonable success with a primal-dual logarithmic barrier method and conjugate-gradient solver.