We study recovery of amplitudes and nodes of a finite impulse train from noisy frequency samples. This problem is known as super-resolution under sparsity constraints and has numerous applications. An especially challenging scenario occurs when the separation between Dirac pulses is smaller than the Nyquist-Shannon-Rayleigh limit. Despite large volumes of research and well-established worst-case recovery bounds, there is currently no known computationally efficient method which achieves these bounds in practice. In this work we combine the well-known Prony's method for exponential fitting with a recently established decimation technique for analyzing the super-resolution problem in the above mentioned regime. We show that our approach attains optimal asymptotic stability in the presence of noise, and has lower computational complexity than the current state of the art methods.
翻译:我们研究从噪声频率样本中恢复有限脉冲列的幅度和节点的问题。这个问题被称为在稀疏约束条件下的超分辨率,具有众多应用。当Dirac脉冲之间的间隔小于Nyquist-Shannon-Rayleigh极限时,尤其具有挑战性的场景会出现。尽管已经有大量的研究和成熟的最坏情况恢复界限,但目前尚无已知的在实践中能够实现这些限制的计算有效方法。在本文中,我们将著名的Prony法用于指数拟合与最近建立的分析超分辨率问题的截频技术相结合。我们证明了在噪声存在的情况下,我们的方法达到了最优的渐近稳定性,并且具有比当前最高级的方法更低的计算复杂度。