{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,16]],"date-time":"2023-12-16T05:58:03Z","timestamp":1702706283033},"reference-count":33,"publisher":"American Mathematical Society (AMS)","issue":"327","license":[{"start":{"date-parts":[[2021,9,9]],"date-time":"2021-09-09T00:00:00Z","timestamp":1631145600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

We consider a reconstruction problem for \u201cspike-train\u201d signals \n\n \n F<\/mml:mi>\n F<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> of an a priori known form \n\n \n \n F<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n j<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n \n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:munderover>\n \n a<\/mml:mi>\n \n j<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \u03b4<\/mml:mi>\n \n (<\/mml:mo>\n x<\/mml:mi>\n \u2212<\/mml:mo>\n \n x<\/mml:mi>\n \n j<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n <\/mml:mrow>\n F(x)=\\sum _{j=1}^{d}a_{j}\\delta \\left (x-x_{j}\\right ),<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> from their moments \n\n \n \n \n m<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n (<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n \u222b<\/mml:mo>\n \n x<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n F<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n d<\/mml:mi>\n x<\/mml:mi>\n .<\/mml:mo>\n <\/mml:mrow>\n m_k(F)=\\int x^kF(x)dx.<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> We assume that the moments \n\n \n \n \n m<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n (<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n m_k(F)<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, \n\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n 2<\/mml:mn>\n d<\/mml:mi>\n \u2212<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n k=0,1,\\ldots ,2d-1<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, are known with an absolute error not exceeding \n\n \n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n \\epsilon > 0<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>. This problem is essentially equivalent to solving the Prony system \n\n \n \n \n \u2211<\/mml:mo>\n \n j<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:munderover>\n \n a<\/mml:mi>\n j<\/mml:mi>\n <\/mml:msub>\n \n x<\/mml:mi>\n j<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msubsup>\n =<\/mml:mo>\n \n m<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n (<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n ,<\/mml:mo>\n \u00a0<\/mml:mtext>\n k<\/mml:mi>\n =<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n 2<\/mml:mn>\n d<\/mml:mi>\n \u2212<\/mml:mo>\n 1.<\/mml:mn>\n <\/mml:mrow>\n \\sum _{j=1}^d a_jx_j^k=m_k(F), \\ k=0,1,\\ldots ,2d-1.<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula><\/p>\n\n

We study the \u201cgeometry of error amplification\u201d in reconstruction of \n\n \n F<\/mml:mi>\n F<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> from \n\n \n \n \n m<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n (<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n ,<\/mml:mo>\n <\/mml:mrow>\n m_k(F),<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> in situations where the nodes \n\n \n \n \n x<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n x<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n x_1,\\ldots ,x_d<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> near-collide, i.e., form a cluster of size \n\n \n \n h<\/mml:mi>\n \u226a<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n h \\ll 1<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>. We show that in this case, error amplification is governed by certain algebraic varieties in the parameter space of signals \n\n \n F<\/mml:mi>\n F<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, which we call the \u201cProny varieties\u201d.<\/p>\n\n

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.<\/p>\n\n

Finally we discuss how to use the geometry of the Prony varieties to improve the reconstruction accuracy given additional a priori information.<\/p>","DOI":"10.1090\/mcom\/3571","type":"journal-article","created":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T18:00:46Z","timestamp":1599674446000},"page":"267-302","source":"Crossref","is-referenced-by-count":2,"title":["Geometry of error amplification in solving the Prony system with near-colliding nodes"],"prefix":"10.1090","volume":"90","author":[{"given":"Andrey","family":"Akinshin","sequence":"first","affiliation":[]},{"given":"Gil","family":"Goldman","sequence":"additional","affiliation":[]},{"given":"Yosef","family":"Yomdin","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2020,9,9]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"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\u2013621. IEEE, 2015.","DOI":"10.1109\/SAMPTA.2015.7148965"},{"key":"2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/699\/14078","article-title":"Accuracy of reconstruction of spike-trains with two near-colliding nodes","author":"Akinshin, Andrey","year":"2017"},{"key":"3","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.21236\/ADA104530"},{"key":"4","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2017.03.026","article-title":"Accurate solution of near-colliding Prony systems via decimation and homotopy continuation","volume":"681","author":"Batenkov, Dmitry","year":"2017","journal-title":"Theoret. Comput. Sci.","ISSN":"http:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"1","key":"5","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/18M1212197","article-title":"Conditioning of partial nonuniform Fourier matrices with clustered nodes","volume":"41","author":"Batenkov, Dmitry","year":"2020","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Dmitry Batenkov, Benedikt Diederichs, Gil Goldman, and Yosef Yomdin, The spectral properties of Vandermonde matrices with clustered nodes, Linear Algebra Appl. (2020), to appear.","DOI":"10.1016\/j.laa.2020.08.034"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaaa005","article-title":"Super-resolution of near-colliding point sources","author":"Batenkov, Dmitry","year":"2020","journal-title":"Information and Inference: A Journal of the IMA","ISSN":"http:\/\/id.crossref.org\/issn\/2049-8772","issn-type":"print"},{"issue":"1","key":"8","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/110836584","article-title":"On the accuracy of solving confluent Prony systems","volume":"73","author":"Batenkov, Dmitry","year":"2013","journal-title":"SIAM J. Appl. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0036-1399","issn-type":"print"},{"key":"9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10958-014-2031-8","article-title":"Geometry and singularities of the Prony mapping","volume":"10","author":"Batenkov, Dmitry","year":"2014","journal-title":"J. Singul."},{"key":"10","unstructured":"Emmanuel J. Cand\u00e8s, private communication. 2014."},{"key":"11","unstructured":"Laurent Demanet and Nam Nguyen, The recoverability limit for superresolution via sparsity, arXiv:1502.01385, 2015."},{"issue":"5","key":"12","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1137\/0523074","article-title":"Superresolution via sparsity constraints","volume":"23","author":"Donoho, David L.","year":"1992","journal-title":"SIAM J. Math. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/0036-1410","issn-type":"print"},{"key":"13","unstructured":"Albert Fannjiang, Compressive Spectral Estimation with Single-Snapshot ESPRIT: Stability and Resolution, arXiv:1607.01827, July 2016."},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4310\/amsa.2017.v2.n2.a2","article-title":"Doubling coverings of algebraic hypersurfaces","volume":"2","author":"Friedland, Omer","year":"2017","journal-title":"Pure Appl. Funct. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/2189-3756","issn-type":"print"},{"key":"15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF01386302","article-title":"On inverses of Vandermonde and confluent Vandermonde matrices","volume":"4","author":"Gautschi, Walter","year":"1962","journal-title":"Numer. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"16","doi-asserted-by":"publisher","first-page":"409","DOI":"10.5427\/jsing.2018.18u","article-title":"Accuracy of noisy spike-train reconstruction: a singularity theory point of view","volume":"18","author":"Goldman, Gil","year":"2018","journal-title":"J. Singul."},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"257","DOI":"10.4310\/MAA.2018.v25.n3.a5","article-title":"Geometry and singularities of Prony varieties","volume":"25","author":"Goldman, Gil","year":"2018","journal-title":"Methods Appl. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/1073-2772","issn-type":"print"},{"key":"18","isbn-type":"print","volume-title":"Vector calculus, linear algebra, and differential forms","author":"Hubbard, John Hamal","year":"1999","ISBN":"http:\/\/id.crossref.org\/isbn\/0136574467"},{"issue":"5","key":"19","doi-asserted-by":"publisher","first-page":"1306","DOI":"10.1007\/s00041-017-9571-5","article-title":"Prony\u2019s method under an almost sharp multivariate Ingham inequality","volume":"24","author":"Kunis, Stefan","year":"2018","journal-title":"J. Fourier Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/1069-5869","issn-type":"print"},{"key":"20","first-page":"1","article-title":"On the condition number of Vandermonde matrices with pairs of nearly-colliding nodes","author":"Kunis, Stefan","year":"2020","journal-title":"Numerical Algorithms"},{"key":"21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.laa.2020.06.003","article-title":"On the smallest singular value of multivariate Vandermonde matrices with clustered nodes","volume":"604","author":"Kunis, Stefan","year":"2020","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"22","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.laa.2015.10.023","article-title":"A multivariate generalization of Prony\u2019s method","volume":"490","author":"Kunis, Stefan","year":"2016","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"23","unstructured":"Weilin Li and Wenjing Liao, Stable super-resolution limit and smallest singular value of restricted Fourier matrices, arXiv:1709.03146, 2017."},{"key":"24","unstructured":"Weilin Li, Wenjing Liao, and Albert Fannjiang, Super-resolution limit of the ESPRIT algorithm, arXiv:1905.03782, 2019."},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.acha.2014.12.003","article-title":"MUSIC for single-snapshot spectral estimation: stability and super-resolution","volume":"40","author":"Liao, Wenjing","year":"2016","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"26","doi-asserted-by":"crossref","unstructured":"Jari Lindberg, Mathematical concepts of optical superresolution, Journal of Optics, 14(8):083001, 2012.","DOI":"10.1088\/2040-8978\/14\/8\/083001"},{"key":"27","unstructured":"Victor Pereyra and Godela Scherer, Exponential Data Fitting and Its Applications, Bentham Science Publishers, January 2010."},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"025001","DOI":"10.1088\/0266-5611\/29\/2\/025001","article-title":"A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators","volume":"29","author":"Peter, Thomas","year":"2013","journal-title":"Inverse Problems","ISSN":"http:\/\/id.crossref.org\/issn\/0266-5611","issn-type":"print"},{"issue":"2","key":"29","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1002\/gamm.201410011","article-title":"Prony methods for recovery of structured functions","volume":"37","author":"Plonka, Gerlind","year":"2014","journal-title":"GAMM-Mitt.","ISSN":"http:\/\/id.crossref.org\/issn\/0936-7195","issn-type":"print"},{"key":"30","doi-asserted-by":"crossref","unstructured":"Daniel Potts and Manfred Tasche, Parameter estimation for exponential sums by approximate Prony method, Signal Processing, 90(4):1631\u20131642, 2010.","DOI":"10.1016\/j.sigpro.2009.11.012"},{"key":"31","unstructured":"R. Prony, Essai experimental et analytique, J. Ec. Polytech.(Paris), 2:24\u201376, 1795."},{"key":"32","unstructured":"P. Stoica and R. L. Moses, Spectral Analysis of Signals, Pearson\/Prentice Hall, 2005."},{"issue":"6","key":"33","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1109\/TSP.2002.1003065","article-title":"Sampling signals with finite rate of innovation","volume":"50","author":"Vetterli, Martin","year":"2002","journal-title":"IEEE Trans. Signal Process.","ISSN":"http:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2021-90-327\/S0025-5718-2020-03571-6\/S0025-5718-2020-03571-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T08:37:27Z","timestamp":1627634247000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2021-90-327\/S0025-5718-2020-03571-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,9]]},"references-count":33,"journal-issue":{"issue":"327","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0025-5718-2020-03571-6"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3571","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,9]]}}}