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