Table of Links
1.1 ESPRIT algorithm and central limit error scaling
1.4 Technical overview and 1.5 Organization
2 Proof of the central limit error scaling
3 Proof of the optimal error scaling
4 Second-order eigenvector perturbation theory
5 Strong eigenvector comparison
5.1 Construction of the “good” P
5.2 Taylor expansion with respect to the error terms
5.3 Error cancellation in the Taylor expansion
C Deferred proofs for Section 2
D Deferred proofs for Section 4
E Deferred proofs for Section 5
F Lower bound for spectral estimation
Abstract
1 Introduction
Spectral estimation is a fundamental problem in statistical signal processing. The goal of spectral estimation is to reconstruct fine details of a signal from noisy measurements. Algorithms for spectral estimation have broad applications spanning image/audio processing and compression [GNHB08], acoustics and electromagnetics [KV96, Sch86], geophysics [SSF90], inverse problems [Fan10, FSY10], time series analysis [SM08], spectrometry [SCGM96], machine learning [HBH+18, QGR+22], and quantum computing [Som19, LT22].
[HBH+18, QGR+22], and quantum computing [Som19, LT22]. In this paper, we will consider the following formulation of the spectral estimation problem: Consider a positive spectral measure
A. Separation of locations. All dominant locations are separated from each other and from non-dominant locations:
It is important to note that separation between non-dominant locations is not required.
B. Separation of intensities. We assume the intensities are positive and ordered
We assume the cumulative intensity of non-dominant locations is bounded:
This setup is directly motivated by the eigenvalue estimation problem on quantum computers, which has received significant attention recently [Som19, SHT22, DTO22, LT22, WFZ+23, WBC22, LNY23, SCS+23, DL23]. We also expect that this setup could be applicable in many fields, such as communication, sensing, and audio processing.
In this paper, we focus on the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm [PRK86]. Since its introduction in 1986, the ESPRIT algorithm has proven one of the most effective methods for spectral estimation in practice. The main question of this paper is as follows:
The main contribution of this paper is a significant improvement over the central limit error scaling outlined in Theorem 1.2. We establish that ESPRIT achieves the optimal error scaling for estimating dominant locations and dominant intensities (Theorem 1.4). To our knowledge, this is the first demonstration of a noisy super-resolution scaling (in the sense of Definition 1.1) for spectral estimation under comparable assumptions.
This paper is available on arxiv under CC BY 4.0 DEED license.
[2] Our use of the term “noisy super-resolution scaling” differs from that in [Moi15], where the term refers to classical super-resolution scaling in the presence of small noise.
Authors:
(1) Zhiyan Ding, Department of Mathematics, University of California, Berkeley;
(2) Ethan N. Epperly, Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA;
(3) Lin Lin, Department of Mathematics, University of California, Berkeley, Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, and Challenge Institute for Quantum Computation, University of California, Berkeley;
(4) Ruizhe Zhang, Simons Institute for the Theory of Computing.
