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 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. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 1.1 ESPRIT algorithm and central limit error scaling 1.1 ESPRIT algorithm and central limit error scaling 1.2 Contribution 1.2 Contribution 1.3 Related work 1.3 Related work 1.4 Technical overview and 1.5 Organization 1.4 Technical overview and 1.5 Organization 2 Proof of the central limit error scaling 2 Proof of the central limit error scaling 3 Proof of the optimal error scaling 3 Proof of the optimal error scaling 4 Second-order eigenvector perturbation theory 4 Second-order eigenvector perturbation theory 5 Strong eigenvector comparison 5 Strong eigenvector comparison 5.1 Construction of the “good” P 5.1 Construction of the “good” P 5.2 Taylor expansion with respect to the error terms 5.2 Taylor expansion with respect to the error terms 5.3 Error cancellation in the Taylor expansion 5.3 Error cancellation in the Taylor expansion 5.4 Proof of Theorem 5.1 5.4 Proof of Theorem 5.1 A Preliminaries A Preliminaries B Vandermonde matrice B Vandermonde matrice C Deferred proofs for Section 2 C Deferred proofs for Section 2 D Deferred proofs for Section 4 D Deferred proofs for Section 4 E Deferred proofs for Section 5 E Deferred proofs for Section 5 F Lower bound for spectral estimation F Lower bound for spectral estimation References 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 Theorem 3.1 (Optimal error scaling of ESPRIT Consider the spectral estimation problem under assumptions Assume If we further assume If we further assume then the location estimation satisfies: then the location estimation satisfies: and the intensity estimation of ESPRIT 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). Note that the permutation in the definition of the matching distance is the same for both Eqs. Proof of Theorem 3.1. We prove the error scaling of the location estimation and intensity estimation of the ESPRIT algorithm below. Proof of Theorem 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. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv 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. Authors: 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.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Strong Eigenvector Comparison for Optimal ESPRIT Convergence

Second-Order Eigenvector Perturbation Theory for ESPRIT Analysis

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Get Free Unlimited IP Geo Data With IPinfo Lite

Proof of Optimal Error Scaling for ESPRIT Algorithm

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

The ESPRIT Algorithm and Central Limit Error Scaling

Proof of Central Limit Error Scaling for ESPRIT Algorithm

Second-Order Eigenvector Perturbation Theory for ESPRIT Analysis

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

The ESPRIT Algorithm and Central Limit Error Scaling

Proof of Central Limit Error Scaling for ESPRIT Algorithm

Second-Order Eigenvector Perturbation Theory for ESPRIT Analysis

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps