This paper develops a mathematical theory of super-resolution. Broadly
speaking, super-resolution is the problem of recovering the fine details of an
object---the high end of its spectrum---from coarse scale information
only---from samples at the low end of the spectrum. Suppose we have many point
sources at unknown locations in $[0,1]$ and with unknown complex-valued
amplitudes. We only observe Fourier samples of this object up until a frequency
cut-off $f_c$. We show that one can super-resolve these point sources with
infinite precision---i.e. recover the exact locations and amplitudes---by
solving a simple convex optimization problem, which can essentially be
reformulated as a semidefinite program. This holds provided that the distance
between sources is at least $2/f_c$. This result extends to higher dimensions
and other models. In one dimension for instance, it is possible to recover a
piecewise smooth function by resolving the discontinuity points with infinite
precision as well. We also show that the theory and methods are robust to
noise. In particular, in the discrete setting we develop some theoretical
results explaining how the accuracy of the super-resolved signal is expected to
degrade when both the noise level and the {\em super-resolution factor} vary.

本文通过解决凸优化问题，展示了如何利用傅里叶采样和半定规划方法以无限精确度解决超分辨率问题，应用到一维的情况中，也可以超分辨率地解决具有分段平滑函数的问题，并且该理论和方法是鲁棒的，能够处理噪声。

超分辨率数学理论探究

Towards a Mathematical Theory of Super-Resolution

Suppose we wish to recover an n-dimensional real-valued vector x_0 (e.g. a
digital signal or image) from incomplete and contaminated observations y = A
x_0 + e; A is a n by m matrix with far fewer rows than columns (n << m) and e
is an error term. Is it possible to recover x_0 accurately based on the data y?
To recover x_0, we consider the solution x* to the l1-regularization problem
min \|x\|_1 subject to \|Ax-y\|_2 <= epsilon, where epsilon is the size of the
error term e. We show that if A obeys a uniform uncertainty principle (with
unit-normed columns) and if the vector x_0 is sufficiently sparse, then the
solution is within the noise level \|x* - x_0\|_2 \le C epsilon.
As a first example, suppose that A is a Gaussian random matrix, then stable
recovery occurs for almost all such A's provided that the number of nonzeros of
x_0 is of about the same order as the number of observations. Second, suppose
one observes few Fourier samples of x_0, then stable recovery occurs for almost
any set of p coefficients provided that the number of nonzeros is of the order
of n/[\log m]^6. In the case where the error term vanishes, the recovery is of
course exact, and this work actually provides novel insights on the exact
recovery phenomenon discussed in earlier papers. The methodology also explains
why one can also very nearly recover approximately sparse signals.

本文中提出了一种压缩感知技术，通过 l1 - 正则化问题来恢复高维实向量 x_0，证明了只要 A 满足均匀不确定原理并且 x_0 具有足够的稀疏性，则可以在噪声水平内准确恢复 x_0，并给出了两个实例。