Noisy Super-Resolution and Optimal Error Scaling for the ESPRIT Algorithm

Subspace-based signal processing techniques, such as the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm, are popular methods for spectral estimation. These algorithms can achieve the so-called super-resolution scaling under low noise conditions, surpassing the well-known Nyquist limit. However, the performance of these algorithms under high-noise conditions is not as well understood. Existing state-of-the-art analysis indicates that ESPRIT and related algorithms can be resilient even for signals where each observation is corrupted by statistically independent, mean-zero noise of size O(1), but these analyses only show that the error ε decays at a slow rate ε ~ n^{−1/2} with respect to the cutoff frequency n (i.e., the maximum frequency of the measurements). In this talk, I will show that the ESPRIT algorithm can achieve a significantly improved error scaling ε ~ n^{−3/2}, exhibiting noisy super-resolution scaling beyond the Nyquist limit ε ~ n^{−1} given by the Nyquist-Shannon sampling theorem. We also established an information-theoretic lower bound, which shows that this scaling is optimal. Our results are derived using novel matrix perturbation techniques, and I will talk about some of the key ideas behind our proof. Additionally, I will discuss an application of this optimal error scaling of the ESPRIT algorithm to early fault-tolerant quantum phase estimation.This is based on joint work with Zhiyan Ding, Ethan N. Epperly, and Lin Lin (https://arxiv.org/abs/2404.03885).