Super-resolution of near-colliding point sources. (11th May 2020)

• Record Type: Journal Article
• Authors: Batenkov, Dmitry; Goldman, Gil; Yomdin, Yosef
• Is Part Of: Information and inference. Volume 10:Number 2(2021)
• Page Start: 515
• Page End: 572
• Publication Date: 2020-05-11
• Subjects: signal reconstruction -- spike-trains -- Fourier transform -- Prony systems -- sparsity -- super-resolution; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iaaa005
• Languages: English
• ISSNs: 2049-8764

Abstract

Abstract: We consider the problem of stable recovery of sparse signals of the form $$\begin{equation*}F(x)=\sum_{j=1}^d a_j\delta(x-x_j), \quad x_j\in\mathbb{R}, \;a_j\in\mathbb{C}, \end{equation*}$$ from their spectral measurements, known in a bandwidth $\varOmega $ with absolute error not exceeding $\epsilon>0$ . We consider the case when at most $p\leqslant d$ nodes $\{x_j\}$ of $F$ form a cluster whose extent is smaller than the Rayleigh limit ${1\over \varOmega }$, while the rest of the nodes is well separated. Provided that $\epsilon \lessapprox \operatorname{SRF}^{-2p+1}$, where $\operatorname{SRF}=(\varOmega \varDelta )^{-1}$ and $\varDelta $ is the minimal separation between the nodes, we show that the minimax error rate for reconstruction of the cluster nodes is of order ${1\over \varOmega }\operatorname{SRF}^{2p-1}\epsilon $, while for recovering the corresponding amplitudes $\{a_j\}$ the rate is of the order $\operatorname{SRF}^{2p-1}\epsilon $ . Moreover, the corresponding minimax rates for the recovery of the non-clustered nodes and amplitudes are ${\epsilon \over \varOmega }$ and $\epsilon $, respectively. These results suggest that stable super-resolution is possible in much more general situations than previously thought. Our numerical experiments show that the well-known matrix pencil method achieves the above accuracy bounds.