Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information
Robust uncertainty principles:: Exact signal reconstruction from highly incomplete frequency information
复制标题
DOI：
10.1109/tit.2005.862083
复制
发表时间：
2006-02-01
影响因子：
2.5
通讯作者：
Tao, T
中科院分区：
文献类型：
--
作者：
Candès, EJ;Romberg, J;Tao, T
本文研究了从不完全频率样本中重建目标的模型问题。考虑离散时间信号f是C-N的元素和随机选择的频率集合Q。是否有可能从集合Q上的傅立叶系数的部分知识中重建f？本文的一个典型结果如下。设f是垂直条T的叠加垂直条尖峰f（t）= E-tau是T的一个元素f（tau）delta（t-tau）服从垂直条T垂直条0.我们不知道尖峰的位置和幅度。然后以至少1 - O（N-m）的概率，f可以被精确地重构为l（1）最小化问题的解min/g Sigma（N-1）/t=0 vertical bar g（t）vertical bar，s.t. (g)overcap（Ω）=（f）overcap（Ω）对于a1 Ω是Ω的一个元素简而言之，通过求解凸优化问题可以获得精确的恢复。我们给出了Cm的数值，该数值取决于所需的成功概率。我们的结果可以解释为一种新的非线性采样定理。实际上，它说，由垂直条T垂直条尖峰构成的任何信号都可以通过凸规划从大小为O（垂直条T垂直条（.）log N）。此外，这在以下意义上几乎是最优的：以概率1 - O（N-M）成功的任何方法通常将需要至少与垂直条T垂直条（.）该方法扩展到各种其他情况和更高的维度。例如，我们展示了如何从不完整的频率样本中重建一个分段常数（一维或二维）对象，前提是跳跃（不连续）的数量服从上述条件，通过最小化其他凸泛函，如f的总变差。
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f is an element of C-N and a randomly chosen set of frequencies Q. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set Q? A typical result of this paper is as follows. Suppose that f is a superposition of vertical bar T vertical bar spikes f(t) = E-tau is an element of T f(tau)delta(t - tau) obeyingvertical bar T vertical bar 0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1 - O(N-m), f can be reconstructed exactly as the solution to the l(1) minimization problemmin/g Sigma(N-1)/t=0 vertical bar g(t)vertical bar, s.t. (g) over cap(omega) = (f) over cap(omega) for al omega is an element of ohmIn short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for Cm which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of vertical bar T vertical bar spikes may be recovered by convex programming from almost every set of frequencies of size O(vertical bar T vertical bar (.) log N). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1 - O(N-M) would in general require a number of frequency samples at least proportional to vertical bar T vertical bar (.) log N.The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples-provided that the number of jumps (discontinuities) obeys the condition above-by minimizing other convex functionals such as the total variation of f.