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 4 Second-order eigenvector perturbation theory In this section, we provide a formal statement of the second-order eigenvector perturbation result in Lemma 1.8. We outline the main steps involved in proving this lemma and defer technical details to Appendix D. In the following part of this section, we always assume Eq. (1.3), Eq. (1.4), and Theorem 3.1 Eq. (3.1) and omit these conditions later. Proposition 4.2 (Expansion of spectral projector). It holds that Proposition 4.2 (Expansion of spectral projector). It holds that The series expansion in Proposition 4.2 is rather nontransparent, as the higher-order terms are expressed in terms of contour integrals. Fortunately, these integrals can be evaluated exactly, leading to explicit formulas for all terms in the expansion in terms of Schur polynomials. As the results are rather intricate, so we defer the statement and proof to Appendix D.1. We can then bound the higher-order terms in this expression, yielding the following representation: Lemma 4.3 (Expansion of spectral projector, simplified). It holds that Lemma 4.3 (Expansion of spectral projector, simplified). It holds that Thus, we can write where R is the remainder matrix of norm The RHS becomes Comparing LHS and RHS with Eq. (4.9), we see that Now, we estimate Summing over k, we get that The proof of the lemma is then completed. 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.

Quant

Proof of Optimal Error Scaling for ESPRIT Algorithm

Proof of Central Limit Error Scaling for ESPRIT Algorithm

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

Second-Order Eigenvector Perturbation Theory for ESPRIT Analysis

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

Proof of Optimal Error Scaling for ESPRIT Algorithm

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

Proof of Optimal Error Scaling for ESPRIT Algorithm

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps