Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Table of Links

Abstract and 1 Introduction

1.1 ESPRIT algorithm and central limit error scaling

1.2 Contribution

1.3 Related work

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

5.4 Proof of Theorem 5.1

A Preliminaries

B Vandermonde matrice

C Deferred proofs for Section 2

D Deferred proofs for Section 4

E Deferred proofs for Section 5

F Lower bound for spectral estimation

References

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.

[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.