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 E Deferred proofs for Section 5 E.1 Proof for Step 1: Construction of the “good” P which gives the expression of P Eq. (5.2) in the lemma. Property I and II follow from Claim E.2. The proof of the lemma is then complete E.1.1 Technical claims Proof. Note that For the first term, we have For the second term, we have Combining them together, we have The claim is then proceed. Claim E.2 (Properties of the “good” P). The invertible matrix P defined by Eq. (5.2) satisfies the following properties: Proof. We prove each of the properties below. Proof of Property I: By the definition of P (Eq. (5.2)), we have Proof of Property II: Consider E.2 Proofs for Step 2: Taylor expansion with respect to the error terms Lemma 5.3. Let P be defined as Eq. (5.2). Then, we have By Claim E.4, the Neumann series in Eq. (E.10) can be truncated up to second order: And for the residual term, we have Finally, combining Eqs. (E.11) to (E.14) together, we obtain that where we re-group the terms in the second step. The proof of the lemma is completed. Lemma 5.4. It holds that Proof. We first deal with the first order term in Eq. (5.8): To bound (I), we notice Combining this and Eq. (5.4), we obtain Next, we keep (II) and first consider the second-order term in Eq. (5.8), which can be rewritten as follows: where the first two steps follow from re-grouping the terms, and the last step follows from Eq. (E.22) and Eq. (E.17). Plugging the bounds for the first order and the second order terms into Eq. (5.8), we get that which proves the lemma. E.2.1 Technical claims where the first step follows from Eq. (1.13) that the second step follows from triangle inequality, and the third step follows from Lemma 1.7 and Corollary B.2. This implies that Claim E.4 (Neumann series truncation). It holds that Proof. For the Neumann series term in Eq. (E.10): we first bound the middle bracket: The first-order term (i.e., k = 1) in Eq. (E.21) can be approximated as follows: where the first step follows from triangle inequality, the second step follows from Eq. (E.18) and Eq. (E.22), and the last step is by direct calculation. By a similar calculation, we can show that the second-order term (i.e., k = 2) in Eq. (E.21) can be approximated by Indeed, this term can be further simplified: where the first step follows from triangle inequality, the second step follows from Eq. (E.18) and Eq. (E.22), and the last step follows from the geometric summation. Combining Eq. (E.23) to Eq. (E.26) together, we get that The claim is then proved. E.3 Proofs for Step 3: Error cancellation in the Taylor expansion E.3.1 Establishing the first equation in Eq. (5.10) Proof. In this proof, we often use the following observations: They are proved in Claim E.5. we have where the third step uses Lemma 1.7 for the first term, Eq. (C.1) for the second term, Lemma C.1 for the third term, Eq. (1.14) for the fifth and seventh terms, Eq. (B.2) for the sixth term. Thus, To bound the second term in the above equation, for any k ≥ 0, we have Therefore, we obtain that Similarly, we also have Plugging Eq. (E.30) into Eq. (E.28) and Eq. (E.29), we have The proof of the lemma is completed. Lemma 5.6. Proof. We analyze Eq. (5.13b) and Eq. (5.13c) column-by-column. Combining the above two equations together and summing over k, we obtain that By Eq. (5.13b) and Eq. (5.13c), we have Without loss of generality, we only consider the first column of Eq. (E.33): where the second step follows from the Toeplize structure of the matrix. Therefore, by triangle inequality, where the second step follows from Eq. (E.35)-Eq. (E.37). Now, we consider the first term of F1. Define where the second step follows from Eq. (E.39). The above two equations imply that Plugging in the values of k = 0 in Eq. (E.35) and Eq. (E.36), we obtain for any k > 0 which implies that Thus, we obtain that Combining Eq. (E.44) and Eq. (E.45) together, the lemma is proved. Lemma 5.9. Then, we bound Eq. (E.50) and Eq. (E.51) separately. For Eq. (E.50), we have For Eq. (E.51), we notice that Hence, combining Eq. (E.52) and Eq. (E.53) together, we obtain Therefore, we complete the proof of the lemma. E.3.3 Technical claims Thus, LHS of Eq. (E.55) can be expressed as: By a slightly modified proof of Corollary B.2, it is easy to show that Together with Lemma 1.7, we obtain that which proves the first part of the claim. Next, we prove Eq. (E.55b). When k = 0, Eq. (E.55b) becomes which follows from Lemma 1.7. When k ≥ 1, we have Similarly, the second term can be bounded by: The third term can be bounded by: Hence, to prove Eq. (E.55b), it suffices to bound where the first step follows from Lemma 1.7, and the second step follows from Eq. (1.14). Combining the above three equations together, we obtain where the second step follows from using Corollary B.3. This proves the k = 1 case of Eq. (E.55b). Finally, by induction Eqs. (E.56) to (E.59), we can prove that for any k ≥ 2, This concludes the proof of Eq. (E.55b). Claim E.6. The claim then follows. 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 E Deferred proofs for Section 5 E.1 Proof for Step 1: Construction of the “good” P which gives the expression of P Eq. (5.2) in the lemma. Property I and II follow from Claim E.2. The proof of the lemma is then complete E.1.1 Technical claims E.1.1 Technical claims Proof . Note that Proof For the first term, we have For the second term, we have Combining them together, we have The claim is then proceed. Claim E.2 (Properties of the “good” P). The invertible matrix P defined by Eq. (5.2) satisfies the following properties: Claim E.2 (Properties of the “good” P). The invertible matrix P defined by Eq. (5.2) satisfies the following properties: Proof . We prove each of the properties below. Proof Proof of Property I: Proof of Property I: By the definition of P (Eq. (5.2)), we have Proof of Property II: Proof of Property II: Consider E.2 Proofs for Step 2: Taylor expansion with respect to the error terms Lemma 5.3. Let P be defined as Eq. (5.2). Then, we have Lemma 5.3. Let P be defined as Eq. (5.2). Then, we have By Claim E.4, the Neumann series in Eq. (E.10) can be truncated up to second order: And for the residual term, we have Finally, combining Eqs. (E.11) to (E.14) together, we obtain that where we re-group the terms in the second step. The proof of the lemma is completed. Lemma 5.4. It holds that Lemma 5.4. It holds that Proof . We first deal with the first order term in Eq. (5.8): Proof To bound (I), we notice Combining this and Eq. (5.4), we obtain Next, we keep (II) and first consider the second-order term in Eq. (5.8), which can be rewritten as follows: where the first two steps follow from re-grouping the terms, and the last step follows from Eq. (E.22) and Eq. (E.17). Plugging the bounds for the first order and the second order terms into Eq. (5.8), we get that which proves the lemma. E.2.1 Technical claims E.2.1 Technical claims where the first step follows from Eq. (1.13) that the second step follows from triangle inequality, and the third step follows from Lemma 1.7 and Corollary B.2. This implies that Claim E.4 (Neumann series truncation). It holds that It holds that It holds that Proof . For the Neumann series term in Eq. (E.10): Proof we first bound the middle bracket: The first-order term (i.e., k = 1) in Eq. (E.21) can be approximated as follows: where the first step follows from triangle inequality, the second step follows from Eq. (E.18) and Eq. (E.22), and the last step is by direct calculation. By a similar calculation, we can show that the second-order term (i.e., k = 2) in Eq. (E.21) can be approximated by Indeed, this term can be further simplified: where the first step follows from triangle inequality, the second step follows from Eq. (E.18) and Eq. (E.22), and the last step follows from the geometric summation. Combining Eq. (E.23) to Eq. (E.26) together, we get that The claim is then proved. E.3 Proofs for Step 3: Error cancellation in the Taylor expansion E.3 Proofs for Step 3: Error cancellation in the Taylor expansion E.3.1 Establishing the first equation in Eq. (5.10) E.3.1 Establishing the first equation in Eq. Proof . In this proof, we often use the following observations: Proof They are proved in Claim E.5. we have where the third step uses Lemma 1.7 for the first term, Eq. (C.1) for the second term, Lemma C.1 for the third term, Eq. (1.14) for the fifth and seventh terms, Eq. (B.2) for the sixth term. Thus, To bound the second term in the above equation, for any k ≥ 0, we have Therefore, we obtain that Similarly, we also have Plugging Eq. (E.30) into Eq. (E.28) and Eq. (E.29), we have The proof of the lemma is completed. Lemma 5.6. Lemma 5.6. Proof . We analyze Eq. (5.13b) and Eq. (5.13c) column-by-column. Proof Combining the above two equations together and summing over k, we obtain that By Eq. (5.13b) and Eq. (5.13c), we have Without loss of generality, we only consider the first column of Eq. (E.33): where the second step follows from the Toeplize structure of the matrix. Therefore, by triangle inequality, where the second step follows from Eq. (E.35)-Eq. (E.37). Now, we consider the first term of F1. Define where the second step follows from Eq. (E.39). The above two equations imply that Plugging in the values of k = 0 in Eq. (E.35) and Eq. (E.36), we obtain for any k > 0 which implies that Thus, we obtain that Combining Eq. (E.44) and Eq. (E.45) together, the lemma is proved. Lemma 5.9. Lemma 5.9. Then, we bound Eq. (E.50) and Eq. (E.51) separately. For Eq. (E.50), we have For Eq. (E.51), we notice that Hence, combining Eq. (E.52) and Eq. (E.53) together, we obtain Therefore, we complete the proof of the lemma. E.3.3 Technical claims E.3.3 Technical claims Thus, LHS of Eq. (E.55) can be expressed as: By a slightly modified proof of Corollary B.2, it is easy to show that Together with Lemma 1.7, we obtain that which proves the first part of the claim. Next, we prove Eq. (E.55b). When k = 0, Eq. (E.55b) becomes which follows from Lemma 1.7. When k ≥ 1, we have Similarly, the second term can be bounded by: The third term can be bounded by: Hence, to prove Eq. (E.55b), it suffices to bound where the first step follows from Lemma 1.7, and the second step follows from Eq. (1.14). Combining the above three equations together, we obtain where the second step follows from using Corollary B.3. This proves the k = 1 case of Eq. (E.55b). Finally, by induction Eqs. (E.56) to (E.59), we can prove that for any k ≥ 2, This concludes the proof of Eq. (E.55b). Claim E.6. Claim E.6. The claim then follows. 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

Lower Bound for Spectral Estimation in Noisy Super-Resolution

Explicit Expansion and Bounds of Spectral Projector in ESPRIT Analysis

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

Eigenvector Perturbation in Aligning Matrix Construction for ESPRIT

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Constructing the Aligning Matrix for Optimal ESPRIT Convergence

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

A Guide to Exploiting Unknown Strategies From a Known Bias Set

Constructing the Aligning Matrix for Optimal ESPRIT Convergence

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

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps