Proof of Optimal Error Scaling for ESPRIT Algorithm

tldt arrow

Too Long; Didn't Read

We present the formal proof demonstrating that the ESPRIT algorithm achieves optimal error scaling for both location and intensity estimation in spectral analysis under specific conditions.

People Mentioned

Mention Thumbnail
featured image - Proof of Optimal Error Scaling for ESPRIT Algorithm
Algorithmic Bias (dot tech) HackerNoon profile picture
0-item

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

3 Proof of the optimal error scaling

In this section, we present the formal statement of our main result (Theorem 1.4) and the proof.


Theorem 3.1 (Optimal error scaling of ESPRIT, formal version of Theorem 1.4). Consider the spectral estimation problem under assumptions Eq. (1.3) and Eq. (1.4). Assume α > 1 and



If we further assume



then the location estimation satisfies:



and the intensity estimation of ESPRIT satisfies:



Note that the permutation in the definition of the matching distance is the same for both Eqs. (3.4) and (3.5).



Proof of Theorem 3.1. We prove the error scaling of the location estimation and intensity estimation of the ESPRIT algorithm below.



Then, by Eq. (2.3) in Lemma 2.2, we obtain that



The first location estimation guarantee (Eq. (3.2)) is proved.


If we further assume that a stronger condition on n (Eq. (3.3)) holds, then by Eq. (3.6), we have



where c ∈ (0, 1) that satisfies the condition (Eq. (2.4)) in Lemma 2.2. By Eq. (2.5), we obtain that



The second location estimation guarantee (Eq. (3.4)) is proved.



For the first term in Eq. (3.7), we have



Plugging Eqs. (3.10) and (3.11) back into Eq. (3.9), we obtain



For the second term in Eq. (3.7), using Eq. (3.8) and a similar proof as Proposition C.3, we have




This paper is available on arxiv under CC BY 4.0 DEED license.

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.


Trending Topics

blockchaincryptocurrencyhackernoon-top-storyprogrammingsoftware-developmenttechnologystartuphackernoon-booksBitcoinbooks