Uncertainty principles and ideal atomic decomposition
Uncertainty principles and ideal atomic decomposition
复制标题
DOI：
10.1109/18.959265
复制
发表时间：
2001-11-01
影响因子：
2.5
通讯作者：
Huo, XM
中科院分区：
文献类型：
--
作者：
Donoho, DL;Huo, XM
假设离散时间信号S(T)，0小于或等于t<；N，是取自尖峰序列1({t=r})和正弦信号exp{2pi Iwt/N)/rootN的组合时频字典中的原子的叠加。仅凭S的知识，就能恢复构成S的原子的精确集合吗？由于每个离散时间信号都可以单独表示为尖峰信号的叠加，也可以表示为正弦信号的叠加，因此没有唯一的方法将S表示为尖峰和正弦的总和。我们证明了，如果S可以表示为这个时频字典中原子的高度稀疏叠加，那么S只有一个这样的高度稀疏表示，它可以通过求解最小化所有分解系数的L(1)范数的凸优化问题来获得。这里“高度稀疏”是指N-t+N-w&n；根N/2，其中N-t是时间原子数，N是频率原子数，N是离散时间信号的长度。这一结果背后是一个普遍的L(1)测不准原理，即如果两个碱基相互不相干，则任何非零信号都不可能同时在两个碱基上具有稀疏表示。对于上面的设置，碱基是正弦和尖峰，相互不一致是根据不同基本元素之间的最大内积来衡量的。不确定性原理适用于各种有趣的基对，而不仅仅是正弦和尖峰。这些结果在粗差带限逼近、纠错加密和非协调信源分离等方面具有理想的应用。相关现象适用于具有正弦和小波等基对的实变量函数和具有小波和脊波等基对的两个变量函数。在这些情况下，如果函数f可以用取自两个基的项的充分稀疏叠加来表示，则只有一个这样的稀疏表示；它可以通过最小L(1)范数原子分解来获得。条件“足够稀疏”变成了多尺度条件；例如，第j级的小波数目加上第j个二进频带中的正弦数目加起来小于2(j/2)的常量。
Suppose a discrete-time signal S(t), 0 less than or equal to t < N, is a superposition of atoms taken from a combined time-frequency dictionary made of spike sequences 1({t=r}) and sinusoids exp{2 pi iwt/N)/rootN. Can one recover, from knowledge of S alone, the precise collection of atoms going to make up S? Because every discrete-time signal can be represented as a superposition of spikes alone, or as a superposition of sinusoids alone, there is no unique way of writing S as a sum of spikes and sinusoids in general.We prove that if S is representable as a highly sparse superposition of atoms from this time-frequency dictionary, then there is only one such highly sparse representation of S, and it can be obtained by solving the convex optimization problem of minimizing the l(1) norm of the coefficients among all decompositions. Here "highly sparse" means that N-t + N-w < rootN/2 where N-t is the number of time atoms, N, is the number of frequency atoms, and N is the length of the discrete-time signal.Underlying this result is a general l(1) uncertainty principle which says that if two bases are mutually incoherent, no nonzero signal can have a sparse representation in both bases simultaneously. For the above setting, the bases are sinuosids and spikes, and mutual incoherence is measured in terms of the largest inner product between different basis elements. The uncertainty principle holds for a variety of interesting basis pairs, not just sinusoids and spikes. The results have idealized applications to band-limited approximation with gross errors, to error-correcting encryption, and to separation of uncoordinated sources.Related phenomena hold for functions of a real variable, with basis pairs such as sinusoids and wavelets, and for functions of two variables, with basis pairs such as wavelets and ridgelets. In these settings, if a function f is representable by a sufficiently sparse superposition of terms taken from both bases, then there is only one such sparse representation; it may be obtained by minimum l(1) norm atomic decomposition. The condition "sufficiently sparse" becomes a multiscale condition; for example, that the number of wavelets at level j plus the number of sinusoids in the jth dyadic frequency band are together less than a constant times 2(j/2).