References: Spectral Estimation, Signal Processing, and Quantum Computing

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 References [AAL23] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. In International Conference on Machine Learning, pages 1018–1040. PMLR, 2023. 79 [BCG+12] Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li, and Martin J. Strauss. What’s the frequency, kenneth?: Sublinear fourier sampling off the grid. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 61– 72. Springer Berlin Heidelberg, 2012. 6 [BDGY20] Dmitry Batenkov, Laurent Demanet, Gil Goldman, and Yosef Yomdin. Conditioning of partial nonuniform fourier matrices with clustered nodes. SIAM Journal on Matrix Analysis and Applications, 41(1):199–220, 2020. 79 [BGY21] Dmitry Batenkov, Gil Goldman, and Yosef Yomdin. Super-resolution of near-colliding point sources. Information and Inference: A Journal of the IMA, 10(2):515–572, 2021. 79 [CFG13] Emmanuel J Candès and Carlos Fernandez-Granda. Super-resolution from noisy data. Journal of Fourier Analysis and Applications, 19:1229–1254, 2013. 2, 6 [CFG14] Emmanuel J Candès and Carlos Fernandez-Granda. Towards a mathematical theory of super-resolution. Communications on pure and applied Mathematics, 67(6):906–956, 2014. 6 [CKPS16] Xue Chen, Daniel M. Kane, Eric Price, and Zhao Song. Fourier-Sparse Interpolation without a Frequency Gap. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 741–750, October 2016. ISSN: 0272-5428. 6 [CM21] Sitan Chen and Ankur Moitra. Algorithmic foundations for the diffraction limit. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 490–503, 2021. 6 [CRT06] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489–509, 2006. 2, 6 [DK70] Chandler Davis and W. M. Kahan. The Rotation of Eigenvectors by a Perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1–46, March 1970. Publisher: Society for Industrial and Applied Mathematics. 29 [DL23] Zhiyan Ding and Lin Lin. Simultaneous estimation of multiple eigenvalues with shortdepth quantum circuit on early fault-tolerant quantum computers. Quantum, 7:1136, October 2023. 2, 6 [DN15] Laurent Demanet and Nam Nguyen. The recoverability limit for superresolution via sparsity. arXiv preprint arXiv:1502.01385, 2015. 79 [Don92] David L Donoho. Superresolution via sparsity constraints. SIAM journal on mathematical analysis, 23(5):1309–1331, 1992. 2, 79 [DTO22] Alicja Dutkiewicz, Barbara M. Terhal, and Thomas E. O’Brien. Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits. Quantum, 6:830, 2022. 2, 6 [Fan10] Albert C Fannjiang. Compressive inverse scattering: I. high-frequency simo/miso and mimo measurements. Inverse Problems, 26(3):035008, 2010. 1 [FL23] Zhiyuan Fan and Jian Li. Efficient algorithms for sparse moment problems without separation. In The Thirty Sixth Annual Conference on Learning Theory, pages 3510– 3565. PMLR, 2023. 6 [FSY10] Albert C. Fannjiang, Thomas Strohmer, and Pengchong Yan. Compressed remote sensing of sparse objects. SIAM Journal on Imaging Sciences, 3(3):595–618, 2010. 1 [GHI+13] Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi. Sample-optimal average-case sparse fourier transform in two dimensions. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1258–1265. IEEE, 2013. 6 [Gil22] Michael Gil. On matching distance between eigenvalues of unbounded operators. Constructive Mathematical Analysis, 5:46–53, 03 2022. 30 [GNHB08] Thomas A Gallagher, Alexander J Nemeth, and Lotfi Hacein-Bey. An introduction to the fourier transform: relationship to mri. American journal of roentgenology, 190(5):1396– 1405, 2008. 1 [Gre66] Thomas Nall Eden Greville. Note on the generalized inverse of a matrix product. Siam Review, 8(4):518–521, 1966. 27 [Han87] Per Christian Hansen. The truncated SVD as a method for regularization. BIT Numerical Mathematics, 27:534–553, 1987. 27 [HBH+18] Jae Hyun Han, Kang Min Bae, Seong Kwang Hong, Hyunsin Park, Jun-Hyuk Kwak, Hee Seung Wang, Daniel Juhyung Joe, Jung Hwan Park, Young Hoon Jung, Shin Hur, et al. Machine learning-based self-powered acoustic sensor for speaker recognition. Nano Energy, 53:658–665, 2018. 1 [HIKP12a] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse fourier transform. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 563–578, 2012. 6 [HIKP12b] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Simple and practical algorithm for sparse Fourier transform. In Proceedings of the twenty-third annual ACMSIAM symposium on Discrete Algorithms (SODA), pages 1183–1194. SIAM, 2012. 6 [HJ12] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, October 2012. Google-Books-ID: O7sgAwAAQBAJ. 29 [HK15] Qingqing Huang and Sham M Kakade. Super-resolution off the grid. Advances in Neural Information Processing Systems, 28, 2015. 6 [HS90] Y. Hua and T.K. Sarkar. Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(5):814–824, May 1990. 6 [IK14] Piotr Indyk and Michael Kapralov. Sample-optimal Fourier sampling in any constant dimension. In IEEE 55th Annual Symposium onFoundations of Computer Science (FOCS), pages 514–523. IEEE, 2014. 6 [IKP14] Piotr Indyk, Michael Kapralov, and Eric Price. (nearly) sample-optimal sparse fourier transform. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 480–499. SIAM, 2014. 6 [JLS23] Yaonan Jin, Daogao Liu, and Zhao Song. Super-resolution and robust sparse continuous fourier transform in any constant dimension: Nearly linear time and sample complexity. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4667–4767. SIAM, 2023. 6 [JNG+19] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736, 2019. 14 [Kap16] Michael Kapralov. Sparse fourier transform in any constant dimension with nearlyoptimal sample complexity in sublinear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 264–277, 2016. 6 [Kap17] Michael Kapralov. Sample efficient estimation and recovery in sparse FFT via isolation on average. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 651–662. IEEE Computer Society, 2017. 6 [Kat12] Tosio Kato. Perturbation Theory for Linear Operators. Springer Berlin, Heidelberg, 2012. 30 [KP16] Ali Koochakzadeh and Piya Pal. Cramér–rao bounds for underdetermined source localization. IEEE Signal Processing Letters, 23(7):919–923, 2016. 79 [KV96] H. Krim and M. Viberg. Two decades of array signal processing research: the parametric approach. IEEE Signal Processing Magazine, 13(4):67–94, 1996. 1 [KVZ19] Michael Kapralov, Ameya Velingker, and Amir Zandieh. Dimension-independent sparse Fourier transform. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2709–2728. SIAM, 2019. 6 [Lee92] Harry B Lee. The cramér-rao bound on frequency estimates of signals closely spaced in frequency. IEEE Transactions on Signal Processing, 40(6):1507–1517, 1992. 79 [LF16] Wenjing Liao and Albert Fannjiang. Music for single-snapshot spectral estimation: Stability and super-resolution. Applied and Computational Harmonic Analysis, 40(1):33– 67, 2016. 6 [LL21] Weilin Li and Wenjing Liao. Stable super-resolution limit and smallest singular value of restricted fourier matrices. Applied and Computational Harmonic Analysis, 51:118–156, 2021. 79 [LLF20] Weilin Li, Wenjing Liao, and Albert Fannjiang. Super-resolution limit of the esprit algorithm. IEEE Transactions on Information Theory, 66(7):4593–4608, 2020. 2, 6, 8, 10, 11, 79 [LNY23] Haoya Li, Hongkang Ni, and Lexing Ying. Adaptive low-depth quantum algorithms for robust multiple-phase estimation. Phys. Rev. A, 108:062408, Dec 2023. 2, 6 [LRSS15] Jian Li, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. Learning arbitrary statistical mixtures of discrete distributions. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 743–752, 2015. 6 [LT22] Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early faulttolerant quantum computers. PRX Quantum, 3:010318, 2022. 1, 2, 6 [LZGL22] Weilin Li, Zengying Zhu, Weiguo Gao, and Wenjing Liao. Stability and super-resolution of music and esprit for multi-snapshot spectral estimation. IEEE Transactions on Signal Processing, 70:4555–4570, 2022. 2, 6, 79 [Mac15] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford Classic Texts in the Physical Sciences. The Clarendon Press, Oxford University Press, New York, second edition, 2015. With contribution by A. V. Zelevinsky and a foreword by Richard Stanley, Reprint of the 2008 paperback edition [MR1354144]. 39 [Mec07] Mark W. Meckes. On the spectral norm of a random toeplitz matrix. Electronic Communications in Probability, 12:315–325, 2007. 35 [Moi15] Ankur Moitra. Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, STOC ’15, pages 821–830, New York, NY, USA, June 2015. Association for Computing Machinery. 2, 3, 4, 6, 10, 29, 31, 79 [MS24] Cameron Musco and Kshiteej Sheth. Sublinear time low-rank approximation of toeplitz matrices. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5084–5117. SIAM, 2024. 6 [NSW19] Vasileios Nakos, Zhao Song, and Zhengyu Wang. (nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1568–1577. IEEE, 2019. 6 [PGDB95] C. Prony, F.M. Gaspard, and R. De Baron. Essai experimental et analytique. Journal de lécole Polytechnique de Paris, 1795. 6 [PRK86] A. Paulraj, R. Roy, and T. Kailath. A subspace rotation approach to signal parameter estimation. Proceedings of the IEEE, 74(7):1044–1046, 1986. 2 [PS15] Eric Price and Zhao Song. A robust sparse fourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 583– 600. IEEE, 2015. 2, 6, 79 [QGR+22] Mingda Qiao, Guru Guruganesh, Ankit Rawat, Kumar Avinava Dubey, and Manzil Zaheer. A fourier approach to mixture learning. Advances in Neural Information Processing Systems, 35:20850–20861, 2022. 1 [RK89] R. Roy and T. Kailath. ESPRIT-estimation of signal parameters via rotational invariance techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7):984– 995, July 1989. 3, 6 [Sau18] Tomas Sauer. Prony’s method: an old trick for new problems. Snapshots of modern mathematics from Oberwolfach;2018, page 04, 2018. Medium: PDF Publisher: Mathematisches Forschungsinstitut Oberwolfach. 6 [SCGM96] Michael W Senko, Jesse D Canterbury, Shenheng Guan, and Alan G Marshall. A highperformance modular data system for fourier transform ion cyclotron resonance mass spectrometry. Rapid Communications in Mass Spectrometry, 10(14):1839–1844, 1996. 1 [Sch86] R. Schmidt. Multiple emitter location and signal parameter estimation. IEEE Transactions on Antennas and Propagation, 34(3):276–280, 1986. 1, 6 [SCS+23] Yizhi Shen, Daan Camps, Aaron Szasz, Siva Darbha, Katherine Klymko, David B Williams-Young, Norm M Tubman, and Roel Van Beeumen. Estimating eigenenergies from quantum dynamics: A unified noise-resilient measurement-driven approach. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 2, pages 302–303. IEEE, 2023. 2, 6 [SHT22] M E Stroeks, J Helsen, and B M Terhal. Spectral estimation for hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution. New Journal of Physics, 24(10):103024, 2022. 2, 6 [SM08] Petre Stoica and Randolph L. Moses. Introduction To Spectral Analysis, pages 319–350. Springer New York, 2008. 1 [SN89] Petre Stoica and Arye Nehorai. Music, maximum likelihood, and cramer-rao bound. IEEE Transactions on Acoustics, speech, and signal processing, 37(5):720–741, 1989. 3, 6, 79 [SN90] Petre Stoica and Arye Nehorai. Music, maximum likelihood, and cramer-rao bound: further results and comparisons. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(12):2140–2150, 1990. 79 [Som19] Rolando D Somma. Quantum eigenvalue estimation via time series analysis. New J. Phys., 21(12):123025, 2019. 1, 2, 6 [SS90] G. W. Stewart and Ji-guang Sun. Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic Press, 1st edition edition, 1990. 29 [SS10] Elias M Stein and Rami Shakarchi. Complex analysis, volume 2. Princeton University Press, 2010. 40 [SSF90] KP Schwarz, MG Sideris, and R Forsberg. The use of fft techniques in physical geodesy. Geophysical Journal International, 100(3):485–514, 1990. 1 [SSWZ23] Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang. Quartic samples suffice for fourier interpolation. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1414–1425. IEEE, 2023. 6 [TBSR13] Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. Compressed sensing off the grid. IEEE Transactions on Information Theory, 59(11):7465– 7490, 2013. 6 [Tro15] Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1–230, 2015. Publisher: Now Publishers. 35 [WBC22] Kianna Wan, Mario Berta, and Earl T Campbell. Randomized quantum algorithm for statistical phase estimation. Phys. Rev. Lett., 129(3):030503, 2022. 2, 6 [WFZ+23] Guoming Wang, Daniel Stilck França, Ruizhe Zhang, Shuchen Zhu, and Peter D Johnson. Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision. Quantum, 7:1167, 2023. 2, 6 [WY20] Yihong Wu and Pengkun Yang. Optimal estimation of Gaussian mixtures via denoised method of moments. The Annals of Statistics, 48(4):1981 – 2007, 2020. 6 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 References [AAL23] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. In International Conference on Machine Learning, pages 1018–1040. PMLR, 2023. 79 [BCG+12] Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li, and Martin J. Strauss. What’s the frequency, kenneth?: Sublinear fourier sampling off the grid. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 61– 72. Springer Berlin Heidelberg, 2012. 6 [BDGY20] Dmitry Batenkov, Laurent Demanet, Gil Goldman, and Yosef Yomdin. Conditioning of partial nonuniform fourier matrices with clustered nodes. SIAM Journal on Matrix Analysis and Applications, 41(1):199–220, 2020. 79 [BGY21] Dmitry Batenkov, Gil Goldman, and Yosef Yomdin. Super-resolution of near-colliding point sources. Information and Inference: A Journal of the IMA, 10(2):515–572, 2021. 79 [CFG13] Emmanuel J Candès and Carlos Fernandez-Granda. Super-resolution from noisy data. Journal of Fourier Analysis and Applications, 19:1229–1254, 2013. 2, 6 [CFG14] Emmanuel J Candès and Carlos Fernandez-Granda. Towards a mathematical theory of super-resolution. Communications on pure and applied Mathematics, 67(6):906–956, 2014. 6 [CKPS16] Xue Chen, Daniel M. Kane, Eric Price, and Zhao Song. Fourier-Sparse Interpolation without a Frequency Gap. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 741–750, October 2016. ISSN: 0272-5428. 6 [CM21] Sitan Chen and Ankur Moitra. Algorithmic foundations for the diffraction limit. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 490–503, 2021. 6 [CRT06] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489–509, 2006. 2, 6 [DK70] Chandler Davis and W. M. Kahan. The Rotation of Eigenvectors by a Perturbation. III. SIAM Journal on Numerical Analysis, 7(1):1–46, March 1970. Publisher: Society for Industrial and Applied Mathematics. 29 [DL23] Zhiyan Ding and Lin Lin. Simultaneous estimation of multiple eigenvalues with shortdepth quantum circuit on early fault-tolerant quantum computers. Quantum, 7:1136, October 2023. 2, 6 [DN15] Laurent Demanet and Nam Nguyen. The recoverability limit for superresolution via sparsity. arXiv preprint arXiv:1502.01385, 2015. 79 [Don92] David L Donoho. Superresolution via sparsity constraints. SIAM journal on mathematical analysis, 23(5):1309–1331, 1992. 2, 79 [DTO22] Alicja Dutkiewicz, Barbara M. Terhal, and Thomas E. O’Brien. Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits. Quantum, 6:830, 2022. 2, 6 [Fan10] Albert C Fannjiang. Compressive inverse scattering: I. high-frequency simo/miso and mimo measurements. Inverse Problems, 26(3):035008, 2010. 1 [FL23] Zhiyuan Fan and Jian Li. Efficient algorithms for sparse moment problems without separation. In The Thirty Sixth Annual Conference on Learning Theory, pages 3510– 3565. PMLR, 2023. 6 [FSY10] Albert C. Fannjiang, Thomas Strohmer, and Pengchong Yan. Compressed remote sensing of sparse objects. SIAM Journal on Imaging Sciences, 3(3):595–618, 2010. 1 [GHI+13] Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi. Sample-optimal average-case sparse fourier transform in two dimensions. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1258–1265. IEEE, 2013. 6 [Gil22] Michael Gil. On matching distance between eigenvalues of unbounded operators. Constructive Mathematical Analysis, 5:46–53, 03 2022. 30 [GNHB08] Thomas A Gallagher, Alexander J Nemeth, and Lotfi Hacein-Bey. An introduction to the fourier transform: relationship to mri. American journal of roentgenology, 190(5):1396– 1405, 2008. 1 [Gre66] Thomas Nall Eden Greville. Note on the generalized inverse of a matrix product. Siam Review, 8(4):518–521, 1966. 27 [Han87] Per Christian Hansen. The truncated SVD as a method for regularization. BIT Numerical Mathematics, 27:534–553, 1987. 27 [HBH+18] Jae Hyun Han, Kang Min Bae, Seong Kwang Hong, Hyunsin Park, Jun-Hyuk Kwak, Hee Seung Wang, Daniel Juhyung Joe, Jung Hwan Park, Young Hoon Jung, Shin Hur, et al. Machine learning-based self-powered acoustic sensor for speaker recognition. Nano Energy, 53:658–665, 2018. 1 [HIKP12a] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse fourier transform. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 563–578, 2012. 6 [HIKP12b] Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Simple and practical algorithm for sparse Fourier transform. In Proceedings of the twenty-third annual ACMSIAM symposium on Discrete Algorithms (SODA), pages 1183–1194. SIAM, 2012. 6 [HJ12] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, October 2012. Google-Books-ID: O7sgAwAAQBAJ. 29 [HK15] Qingqing Huang and Sham M Kakade. Super-resolution off the grid. Advances in Neural Information Processing Systems, 28, 2015. 6 [HS90] Y. Hua and T.K. Sarkar. Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(5):814–824, May 1990. 6 [IK14] Piotr Indyk and Michael Kapralov. Sample-optimal Fourier sampling in any constant dimension. In IEEE 55th Annual Symposium onFoundations of Computer Science (FOCS), pages 514–523. IEEE, 2014. 6 [IKP14] Piotr Indyk, Michael Kapralov, and Eric Price. (nearly) sample-optimal sparse fourier transform. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 480–499. SIAM, 2014. 6 [JLS23] Yaonan Jin, Daogao Liu, and Zhao Song. Super-resolution and robust sparse continuous fourier transform in any constant dimension: Nearly linear time and sample complexity. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4667–4767. SIAM, 2023. 6 [JNG+19] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736, 2019. 14 [Kap16] Michael Kapralov. Sparse fourier transform in any constant dimension with nearlyoptimal sample complexity in sublinear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 264–277, 2016. 6 [Kap17] Michael Kapralov. Sample efficient estimation and recovery in sparse FFT via isolation on average. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 651–662. IEEE Computer Society, 2017. 6 [Kat12] Tosio Kato. Perturbation Theory for Linear Operators. Springer Berlin, Heidelberg, 2012. 30 [KP16] Ali Koochakzadeh and Piya Pal. Cramér–rao bounds for underdetermined source localization. IEEE Signal Processing Letters, 23(7):919–923, 2016. 79 [KV96] H. Krim and M. Viberg. Two decades of array signal processing research: the parametric approach. IEEE Signal Processing Magazine, 13(4):67–94, 1996. 1 [KVZ19] Michael Kapralov, Ameya Velingker, and Amir Zandieh. Dimension-independent sparse Fourier transform. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2709–2728. SIAM, 2019. 6 [Lee92] Harry B Lee. The cramér-rao bound on frequency estimates of signals closely spaced in frequency. IEEE Transactions on Signal Processing, 40(6):1507–1517, 1992. 79 [LF16] Wenjing Liao and Albert Fannjiang. Music for single-snapshot spectral estimation: Stability and super-resolution. Applied and Computational Harmonic Analysis, 40(1):33– 67, 2016. 6 [LL21] Weilin Li and Wenjing Liao. Stable super-resolution limit and smallest singular value of restricted fourier matrices. Applied and Computational Harmonic Analysis, 51:118–156, 2021. 79 [LLF20] Weilin Li, Wenjing Liao, and Albert Fannjiang. Super-resolution limit of the esprit algorithm. IEEE Transactions on Information Theory, 66(7):4593–4608, 2020. 2, 6, 8, 10, 11, 79 [LNY23] Haoya Li, Hongkang Ni, and Lexing Ying. Adaptive low-depth quantum algorithms for robust multiple-phase estimation. Phys. Rev. A, 108:062408, Dec 2023. 2, 6 [LRSS15] Jian Li, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. Learning arbitrary statistical mixtures of discrete distributions. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, page 743–752, 2015. 6 [LT22] Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early faulttolerant quantum computers. PRX Quantum, 3:010318, 2022. 1, 2, 6 [LZGL22] Weilin Li, Zengying Zhu, Weiguo Gao, and Wenjing Liao. Stability and super-resolution of music and esprit for multi-snapshot spectral estimation. IEEE Transactions on Signal Processing, 70:4555–4570, 2022. 2, 6, 79 [Mac15] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford Classic Texts in the Physical Sciences. The Clarendon Press, Oxford University Press, New York, second edition, 2015. With contribution by A. V. Zelevinsky and a foreword by Richard Stanley, Reprint of the 2008 paperback edition [MR1354144]. 39 [Mec07] Mark W. Meckes. On the spectral norm of a random toeplitz matrix. Electronic Communications in Probability, 12:315–325, 2007. 35 [Moi15] Ankur Moitra. Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, STOC ’15, pages 821–830, New York, NY, USA, June 2015. Association for Computing Machinery. 2, 3, 4, 6, 10, 29, 31, 79 [MS24] Cameron Musco and Kshiteej Sheth. Sublinear time low-rank approximation of toeplitz matrices. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5084–5117. SIAM, 2024. 6 [NSW19] Vasileios Nakos, Zhao Song, and Zhengyu Wang. (nearly) sample-optimal sparse fourier transform in any dimension; ripless and filterless. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1568–1577. IEEE, 2019. 6 [PGDB95] C. Prony, F.M. Gaspard, and R. De Baron. Essai experimental et analytique. Journal de lécole Polytechnique de Paris, 1795. 6 [PRK86] A. Paulraj, R. Roy, and T. Kailath. A subspace rotation approach to signal parameter estimation. Proceedings of the IEEE, 74(7):1044–1046, 1986. 2 [PS15] Eric Price and Zhao Song. A robust sparse fourier transform in the continuous setting. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 583– 600. IEEE, 2015. 2, 6, 79 [QGR+22] Mingda Qiao, Guru Guruganesh, Ankit Rawat, Kumar Avinava Dubey, and Manzil Zaheer. A fourier approach to mixture learning. Advances in Neural Information Processing Systems, 35:20850–20861, 2022. 1 [RK89] R. Roy and T. Kailath. ESPRIT-estimation of signal parameters via rotational invariance techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7):984– 995, July 1989. 3, 6 [Sau18] Tomas Sauer. Prony’s method: an old trick for new problems. Snapshots of modern mathematics from Oberwolfach;2018, page 04, 2018. Medium: PDF Publisher: Mathematisches Forschungsinstitut Oberwolfach. 6 [SCGM96] Michael W Senko, Jesse D Canterbury, Shenheng Guan, and Alan G Marshall. A highperformance modular data system for fourier transform ion cyclotron resonance mass spectrometry. Rapid Communications in Mass Spectrometry, 10(14):1839–1844, 1996. 1 [Sch86] R. Schmidt. Multiple emitter location and signal parameter estimation. IEEE Transactions on Antennas and Propagation, 34(3):276–280, 1986. 1, 6 [SCS+23] Yizhi Shen, Daan Camps, Aaron Szasz, Siva Darbha, Katherine Klymko, David B Williams-Young, Norm M Tubman, and Roel Van Beeumen. Estimating eigenenergies from quantum dynamics: A unified noise-resilient measurement-driven approach. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 2, pages 302–303. IEEE, 2023. 2, 6 [SHT22] M E Stroeks, J Helsen, and B M Terhal. Spectral estimation for hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution. New Journal of Physics, 24(10):103024, 2022. 2, 6 [SM08] Petre Stoica and Randolph L. Moses. Introduction To Spectral Analysis, pages 319–350. Springer New York, 2008. 1 [SN89] Petre Stoica and Arye Nehorai. Music, maximum likelihood, and cramer-rao bound. IEEE Transactions on Acoustics, speech, and signal processing, 37(5):720–741, 1989. 3, 6, 79 [SN90] Petre Stoica and Arye Nehorai. Music, maximum likelihood, and cramer-rao bound: further results and comparisons. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(12):2140–2150, 1990. 79 [Som19] Rolando D Somma. Quantum eigenvalue estimation via time series analysis. New J. Phys., 21(12):123025, 2019. 1, 2, 6 [SS90] G. W. Stewart and Ji-guang Sun. Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic Press, 1st edition edition, 1990. 29 [SS10] Elias M Stein and Rami Shakarchi. Complex analysis, volume 2. Princeton University Press, 2010. 40 [SSF90] KP Schwarz, MG Sideris, and R Forsberg. The use of fft techniques in physical geodesy. Geophysical Journal International, 100(3):485–514, 1990. 1 [SSWZ23] Zhao Song, Baocheng Sun, Omri Weinstein, and Ruizhe Zhang. Quartic samples suffice for fourier interpolation. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1414–1425. IEEE, 2023. 6 [TBSR13] Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. Compressed sensing off the grid. IEEE Transactions on Information Theory, 59(11):7465– 7490, 2013. 6 [Tro15] Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1–230, 2015. Publisher: Now Publishers. 35 [WBC22] Kianna Wan, Mario Berta, and Earl T Campbell. Randomized quantum algorithm for statistical phase estimation. Phys. Rev. Lett., 129(3):030503, 2022. 2, 6 [WFZ+23] Guoming Wang, Daniel Stilck França, Ruizhe Zhang, Shuchen Zhu, and Peter D Johnson. Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision. Quantum, 7:1167, 2023. 2, 6 [WY20] Yihong Wu and Pengkun Yang. Optimal estimation of Gaussian mixtures via denoised method of moments. The Annals of Statistics, 48(4):1981 – 2007, 2020. 6 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.