Performance Analysis of OMP in Super-Resolution

Abstract

Given a spectrally sparse signal $\mathbf{y}={\sum }_{i=1}^s{x}_i\mathbf{f}({\tau }_i)\in {\mathbb{C}}^{2n+1}$ consisting of $s$ complex sinusoids, we consider the super-resolution problem, which is about estimating frequency components $\{{\tau }_i{\}}_{i=1}^s$ of $\mathbf{y}$. We consider the OMP-type algorithms for super-resolution, which is more efficient than other approaches based on Semi-Definite Programming. Our analysis shows that a two-stage algorithm with OMP initialization can recover frequency components under the separation condition $n\Delta \gtrsim \text{dyn}(\mathbf{x})$ and the dependency on $\text{dyn}(\mathbf{x})$ is inevitable for the vanilla OMP algorithm. We further show that the Sliding-OMP algorithm, a variant of the OMP algorithm with an additional refinement step at each iteration, is provable to recover $\{{\tau }_i{\}}_{i=1}^s$ under the separation condition $n\Delta \ge c$. Moreover, our result can be extended to an incomplete measurement model with $O(s^2\log n)$ measurements.

Add numerical experiments