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 Abstract 1 Introduction Spectral estimation is a fundamental problem in statistical signal processing. The goal of spectral estimation is to reconstruct fine details of a signal from noisy measurements. Algorithms for spectral estimation have broad applications spanning image/audio processing and compression [GNHB08], acoustics and electromagnetics [KV96, Sch86], geophysics [SSF90], inverse problems [Fan10, FSY10], time series analysis [SM08], spectrometry [SCGM96], machine learning [HBH+18, QGR+22], and quantum computing [Som19, LT22]. [HBH+18, QGR+22], and quantum computing [Som19, LT22]. In this paper, we will consider the following formulation of the spectral estimation problem: Consider a positive spectral measure A. Separation of locations. All dominant locations are separated from each other and from non-dominant locations: It is important to note that separation between non-dominant locations is not required. B. Separation of intensities. We assume the intensities are positive and ordered We assume the cumulative intensity of non-dominant locations is bounded: This setup is directly motivated by the eigenvalue estimation problem on quantum computers, which has received significant attention recently [Som19, SHT22, DTO22, LT22, WFZ+23, WBC22, LNY23, SCS+23, DL23]. We also expect that this setup could be applicable in many fields, such as communication, sensing, and audio processing. In this paper, we focus on the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm [PRK86]. Since its introduction in 1986, the ESPRIT algorithm has proven one of the most effective methods for spectral estimation in practice. The main question of this paper is as follows: The main contribution of this paper is a significant improvement over the central limit error scaling outlined in Theorem 1.2. We establish that ESPRIT achieves the optimal error scaling for estimating dominant locations and dominant intensities (Theorem 1.4). To our knowledge, this is the first demonstration of a noisy super-resolution scaling (in the sense of Definition 1.1) for spectral estimation under comparable assumptions. This paper is available on arxiv under CC BY 4.0 DEED license. [2] Our use of the term “noisy super-resolution scaling” differs from that in [Moi15], where the term refers to classical super-resolution scaling in the presence of small noise. 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 Abstract 1 Introduction Spectral estimation is a fundamental problem in statistical signal processing. The goal of spectral estimation is to reconstruct fine details of a signal from noisy measurements. Algorithms for spectral estimation have broad applications spanning image/audio processing and compression [GNHB08], acoustics and electromagnetics [KV96, Sch86], geophysics [SSF90], inverse problems [Fan10, FSY10], time series analysis [SM08], spectrometry [SCGM96], machine learning [HBH+18, QGR+22], and quantum computing [Som19, LT22]. [HBH+18, QGR+22], and quantum computing [Som19, LT22]. In this paper, we will consider the following formulation of the spectral estimation problem: Consider a positive spectral measure A. Separation of locations . All dominant locations are separated from each other and from non-dominant locations: Separation of locations It is important to note that separation between non-dominant locations is not required. B. Separation of intensities. We assume the intensities are positive and ordered Separation of intensities. We assume the cumulative intensity of non-dominant locations is bounded: This setup is directly motivated by the eigenvalue estimation problem on quantum computers, which has received significant attention recently [Som19, SHT22, DTO22, LT22, WFZ+23, WBC22, LNY23, SCS+23, DL23]. We also expect that this setup could be applicable in many fields, such as communication, sensing, and audio processing. In this paper, we focus on the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm [PRK86]. Since its introduction in 1986, the ESPRIT algorithm has proven one of the most effective methods for spectral estimation in practice. The main question of this paper is as follows: The main contribution of this paper is a significant improvement over the central limit error scaling outlined in Theorem 1.2. We establish that ESPRIT achieves the optimal error scaling for estimating dominant locations and dominant intensities (Theorem 1.4). To our knowledge, this is the first demonstration of a noisy super-resolution scaling (in the sense of Definition 1.1) for spectral estimation under comparable assumptions. 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 [2] Our use of the term “noisy super-resolution scaling” differs from that in [Moi15], where the term refers to classical super-resolution scaling in the presence of small noise. 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

Optimal Error Scaling of ESPRIT Algorithm Demonstrated

Theoretical Analysis of Fair Data Pruning with Gaussian Mixtures

Bias in Algorithmic Technology Exposed 

Too Long; Didn't Read

Make resilience your competitive advantage

Optimal Error Scaling for ESPRIT in Noisy Spectral Estimation

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

References: Spectral Estimation, Signal Processing, and Quantum Computing

An Improved Method for Quantum Matrix Multiplication: Main Procedure

An Improved Method for Quantum Matrix Multiplication: Applications

Acknowledgements, Declarations, Data Availability Statement, and References

An Improved Method for Quantum Matrix Multiplication: Appendix A

References: Spectral Estimation, Signal Processing, and Quantum Computing

An Improved Method for Quantum Matrix Multiplication: Main Procedure

An Improved Method for Quantum Matrix Multiplication: Applications

Acknowledgements, Declarations, Data Availability Statement, and References

An Improved Method for Quantum Matrix Multiplication: Appendix A

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps