论文标题
超分辨率和稳健的稀疏连续傅立叶变换在任何恒定尺寸上：几乎线性时间和样品复杂性
Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity
论文作者
论文摘要
通过分辨率命名的对象中解决细节的能力是成像系统的核心参数。超分辨率是一类技术，可以增强成像系统的分辨率，甚至超越系统的衍射极限。尽管在应用程序上取得了巨大的成功，但在理论方面，超分辨率尚未得到很好的理解，尤其是对于任何维度$ d \ geq 2 $。特别是，为了恢复$ k $ -sparse信号，所有先前的结果都均均为poly $（k）$样本或运行时间。 我们为在强噪声模型下的任何（常数）维度设计强大的算法，基于在稀疏的傅立叶变换（稀疏FT）中开发一些新技术，例如倒置可靠的线性系统，“蛋壳”采样方案，以及在高维度中的分区和投票方法。对于任何恒定尺寸，这些算法是第一个实现运行时间和样品复杂性（几乎）线性和对数的带宽对数的算法（几乎）线性的，我们相信工作中开发的技术可以在超级分辨率和稀疏FT问题上找到其进一步的应用程序。
The ability to resolve detail in the object that is being imaged, named by resolution, is the core parameter of an imaging system. Super-resolution is a class of techniques that can enhance the resolution of an imaging system and even transcend the diffraction limit of systems. Despite huge success in the application, super-resolution is not well understood on the theoretical side, especially for any dimension $d \geq 2$. In particular, in order to recover a $k$-sparse signal, all previous results suffer from either/both poly$(k)$ samples or running time. We design robust algorithms for any (constant) dimension under a strong noise model based on developing some new techniques in Sparse Fourier transform (Sparse FT), such as inverting a robust linear system, "eggshell" sampling schemes, and partition and voting methods in high dimension. These algorithms are the first to achieve running time and sample complexity (nearly) linear in the number of source points and logarithmic in bandwidth for any constant dimension, and we believe the techniques developed in the work can find their further applications on the Super-resolution and Sparse FT problem.
