Geometry of error amplification in solving the Prony system with near-colliding nodes
HTML articles powered by AMS MathViewer
- by Andrey Akinshin, Gil Goldman and Yosef Yomdin HTML | PDF
- Math. Comp. 90 (2021), 267-302 Request permission
Abstract:
We consider a reconstruction problem for “spike-train” signals $F$ of an a priori known form $F(x)=\sum _{j=1}^{d}a_{j}\delta \left (x-x_{j}\right ),$ from their moments $m_k(F)=\int x^kF(x)dx.$ We assume that the moments $m_k(F)$, $k=0,1,\ldots ,2d-1$, are known with an absolute error not exceeding $\epsilon > 0$. This problem is essentially equivalent to solving the Prony system $\sum _{j=1}^d a_jx_j^k=m_k(F), \ k=0,1,\ldots ,2d-1.$
We study the “geometry of error amplification” in reconstruction of $F$ from $m_k(F),$ in situations where the nodes $x_1,\ldots ,x_d$ near-collide, i.e., form a cluster of size $h \ll 1$. We show that in this case, error amplification is governed by certain algebraic varieties in the parameter space of signals $F$, which we call the “Prony varieties”.
Based on this we produce lower and upper bounds, of the same order, on the worst case reconstruction error. In addition we derive separate lower and upper bounds on the reconstruction of the amplitudes and the nodes.
Finally we discuss how to use the geometry of the Prony varieties to improve the reconstruction accuracy given additional a priori information.
References
- Andrey Akinshin, Dmitry Batenkov, and Yosef Yomdin, Accuracy of spike-train Fourier reconstruction for colliding nodes, 2015 International Conference on Sampling Theory and Applications (SampTA), pages 617–621. IEEE, 2015.
- Andrey Akinshin, Gil Goldman, Vladimir Golubyatnikov, and Yosef Yomdin, Accuracy of reconstruction of spike-trains with two near-colliding nodes, Complex analysis and dynamical systems VII, Contemp. Math., vol. 699, Amer. Math. Soc., Providence, RI, 2017, pp. 1–17. MR 3716100, DOI 10.1090/conm/699/14078
- Jon R Auton and Michael L Van Blaricum, Investigation of procedures for automatic resonance extraction from noisy transient electromagnetics data, Math. Notes, 1:79, 1981.
- Dmitry Batenkov, Accurate solution of near-colliding Prony systems via decimation and homotopy continuation, Theoret. Comput. Sci. 681 (2017), 27–40. MR 3659414, DOI 10.1016/j.tcs.2017.03.026
- Dmitry Batenkov, Laurent Demanet, Gil Goldman, and Yosef Yomdin, Conditioning of partial nonuniform Fourier matrices with clustered nodes, SIAM J. Matrix Anal. Appl. 41 (2020), no. 1, 199–220. MR 4057622, DOI 10.1137/18M1212197
- Dmitry Batenkov, Benedikt Diederichs, Gil Goldman, and Yosef Yomdin, The spectral properties of Vandermonde matrices with clustered nodes, Linear Algebra Appl. (2020), to appear.
- Dmitry Batenkov, Gil Goldman, and Yosef Yomdin, Super-resolution of near-colliding point sources, Information and Inference: A Journal of the IMA , posted on (2020), available at https://academic.oup.com/imaiai/advance-article-pdf/doi/10.1093/imaiai/iaaa005/33483116/iaaa005.pdf. iaaa005., DOI 10.1093/imaiai/iaaa005
- Dmitry Batenkov and Yosef Yomdin, On the accuracy of solving confluent Prony systems, SIAM J. Appl. Math. 73 (2013), no. 1, 134–154. MR 3033143, DOI 10.1137/110836584
- Dmitry Batenkov and Yosef Yomdin, Geometry and singularities of the Prony mapping, J. Singul. 10 (2014), 1–25. MR 3300283, DOI 10.1007/s10958-014-2031-8
- Emmanuel J. Candès, private communication. 2014.
- Laurent Demanet and Nam Nguyen, The recoverability limit for superresolution via sparsity, arXiv:1502.01385, 2015.
- David L. Donoho, Superresolution via sparsity constraints, SIAM J. Math. Anal. 23 (1992), no. 5, 1309–1331. MR 1177792, DOI 10.1137/0523074
- Albert Fannjiang, Compressive Spectral Estimation with Single-Snapshot ESPRIT: Stability and Resolution, arXiv:1607.01827, July 2016.
- Omer Friedland and Yosef Yomdin, Doubling coverings of algebraic hypersurfaces, Pure Appl. Funct. Anal. 2 (2017), no. 2, 221–241. MR 3656264, DOI 10.4310/amsa.2017.v2.n2.a2
- Walter Gautschi, On inverses of Vandermonde and confluent Vandermonde matrices, Numer. Math. 4 (1962), 117–123. MR 139627, DOI 10.1007/BF01386302
- Gil Goldman, Yehonatan Salman, and Yosef Yomdin, Accuracy of noisy spike-train reconstruction: a singularity theory point of view, J. Singul. 18 (2018), 409–426. MR 3899549, DOI 10.5427/jsing.2018.18u
- Gil Goldman, Yehonatan Salman, and Yosef Yomdin, Geometry and singularities of Prony varieties, Methods Appl. Anal. 25 (2018), no. 3, 257–275. MR 4037207, DOI 10.4310/MAA.2018.v25.n3.a5
- John Hamal Hubbard and Barbara Burke Hubbard, Vector calculus, linear algebra, and differential forms, Prentice Hall, Inc., Upper Saddle River, NJ, 1999. A unified approach. MR 1657732
- Stefan Kunis, H. Michael Möller, Thomas Peter, and Ulrich von der Ohe, Prony’s method under an almost sharp multivariate Ingham inequality, J. Fourier Anal. Appl. 24 (2018), no. 5, 1306–1318. MR 3856230, DOI 10.1007/s00041-017-9571-5
- Stefan Kunis and Dominik Nagel, On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes, Numerical Algorithms (2020), 1–24.
- Stefan Kunis and Dominik Nagel, On the smallest singular value of multivariate Vandermonde matrices with clustered nodes, Linear Algebra Appl. 604 (2020), 1–20. MR 4114215, DOI 10.1016/j.laa.2020.06.003
- Stefan Kunis, Thomas Peter, Tim Römer, and Ulrich von der Ohe, A multivariate generalization of Prony’s method, Linear Algebra Appl. 490 (2016), 31–47. MR 3429031, DOI 10.1016/j.laa.2015.10.023
- Weilin Li and Wenjing Liao, Stable super-resolution limit and smallest singular value of restricted Fourier matrices, arXiv:1709.03146, 2017.
- Weilin Li, Wenjing Liao, and Albert Fannjiang, Super-resolution limit of the ESPRIT algorithm, arXiv:1905.03782, 2019.
- Wenjing Liao and Albert Fannjiang, MUSIC for single-snapshot spectral estimation: stability and super-resolution, Appl. Comput. Harmon. Anal. 40 (2016), no. 1, 33–67. MR 3431484, DOI 10.1016/j.acha.2014.12.003
- Jari Lindberg, Mathematical concepts of optical superresolution, Journal of Optics, 14(8):083001, 2012.
- Victor Pereyra and Godela Scherer, Exponential Data Fitting and Its Applications, Bentham Science Publishers, January 2010.
- Thomas Peter and Gerlind Plonka, A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators, Inverse Problems 29 (2013), no. 2, 025001, 21. MR 3011964, DOI 10.1088/0266-5611/29/2/025001
- Gerlind Plonka and Manfred Tasche, Prony methods for recovery of structured functions, GAMM-Mitt. 37 (2014), no. 2, 239–258. MR 3285022, DOI 10.1002/gamm.201410011
- Daniel Potts and Manfred Tasche, Parameter estimation for exponential sums by approximate Prony method, Signal Processing, 90(4):1631–1642, 2010.
- R. Prony, Essai experimental et analytique, J. Ec. Polytech.(Paris), 2:24–76, 1795.
- P. Stoica and R. L. Moses, Spectral Analysis of Signals, Pearson/Prentice Hall, 2005.
- Martin Vetterli, Pina Marziliano, and Thierry Blu, Sampling signals with finite rate of innovation, IEEE Trans. Signal Process. 50 (2002), no. 6, 1417–1428. MR 1930786, DOI 10.1109/TSP.2002.1003065
Additional Information
- Andrey Akinshin
- Affiliation: Department of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel
- MR Author ID: 1061721
- ORCID: 0000-0003-3553-9367
- Email: andrey.akinshin@gmail.com
- Gil Goldman
- Affiliation: Department of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel
- MR Author ID: 1233252
- ORCID: 0000-0002-4087-7320
- Email: gilgoldm@gmail.com
- Yosef Yomdin
- Affiliation: Department of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel
- MR Author ID: 185690
- Email: yosef.yomdin@weizmann.ac.il
- Received by editor(s): March 20, 2018
- Received by editor(s) in revised form: April 22, 2018, May 8, 2019, and October 31, 2019
- Published electronically: September 9, 2020
- Additional Notes: The research of the second and third authors was supported in part by the Minerva Foundation.
- © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 267-302
- MSC (2010): Primary 65H10, 94A12
- DOI: https://doi.org/10.1090/mcom/3571
- MathSciNet review: 4166461