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 B Vandermonde matrice In this section, we discuss results for Vandermonde matrices that will be heavily used throughout our analysis. We begin in Appendix B.1 by discussing Moitra’s bounds [Moi15] for the singular values of a Vandermonde matrix. Then, in Appendix B.2, we present a comparison lemma for the Vandermonde basis and eigenbasis of a Toeplitz matrix B.1 Moitra’s singular value bound For us, one of the core technical tools for analyzing ESPRIT is bound on the singular values of Vandermonde matrices, proven in the seminal work of Moitra [Moi15]. The main result is as follow: This result immediately yields the following useful corollary Corollary B.2 (Vandermonde matrix: Gram matrix and outer product). In the setting of Theorem B. B.2 Vandermonde basis and eigenbasis The exact Toeplitz matrix T Eq. (1.6) has two useful factorizations, each of which packages useful information about the matrix. The first factorization is the eigendecomposition The eigendecomposition is useful because it can be easily computed using standard methods from numerical linear algebra. The second useful factorization is the Vandermonde decomposition The Vandermonde decomposition contains information about the frequency spectrum. However, it can only be computed indirectly, such as by procedures such as ESPRIT which use the eigendecomposition as a subroutine. Recall that A direct consequence of Theorem B.1 is the following estimates for the eigenvalues of T: The lemma is then proved. By the definition of the Vandermonde matrix, 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 B Vandermonde matrice In this section, we discuss results for Vandermonde matrices that will be heavily used throughout our analysis. We begin in Appendix B.1 by discussing Moitra’s bounds [Moi15] for the singular values of a Vandermonde matrix. Then, in Appendix B.2, we present a comparison lemma for the Vandermonde basis and eigenbasis of a Toeplitz matrix B.1 Moitra’s singular value bound For us, one of the core technical tools for analyzing ESPRIT is bound on the singular values of Vandermonde matrices, proven in the seminal work of Moitra [Moi15]. The main result is as follow: This result immediately yields the following useful corollary Corollary B.2 (Vandermonde matrix: Gram matrix and outer product). In the setting of Theorem B. Corollary B.2 (Vandermonde matrix: Gram matrix and outer product). In the setting of Theorem B. B.2 Vandermonde basis and eigenbasis The exact Toeplitz matrix T Eq. (1.6) has two useful factorizations, each of which packages useful information about the matrix. The first factorization is the eigendecomposition The eigendecomposition is useful because it can be easily computed using standard methods from numerical linear algebra. The second useful factorization is the Vandermonde decomposition Vandermonde decomposition The Vandermonde decomposition contains information about the frequency spectrum. However, it can only be computed indirectly, such as by procedures such as ESPRIT which use the eigendecomposition as a subroutine. Recall that A direct consequence of Theorem B.1 is the following estimates for the eigenvalues of T: The lemma is then proved. By the definition of the Vandermonde matrix, 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

Proofs of Central Limit Error Scaling Lemmas for ESPRIT

Mathematical Notations for Spectral Estimation Analysis

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

Vandermonde Matrices in Spectral Estimation Analysis

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

References: Spectral Estimation, Signal Processing, and Quantum Computing

More functional: A story in refactoring a 2d vector library

Programmer’s guide to linear systems

SciPy Cheat Sheet: Linear Algebra in Python

SciPy Tutorial: Linear Algebra

References: Spectral Estimation, Signal Processing, and Quantum Computing

More functional: A story in refactoring a 2d vector library

Programmer’s guide to linear systems

SciPy Cheat Sheet: Linear Algebra in Python

SciPy Tutorial: Linear Algebra

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps