{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T19:04:34Z","timestamp":1767035074442,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T00:00:00Z","timestamp":1552608000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["666981"],"award-info":[{"award-number":["666981"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Adv Comput Math"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s10444-019-09672-2","type":"journal-article","created":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T20:15:08Z","timestamp":1552680908000},"page":"1401-1437","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?"],"prefix":"10.1007","volume":"45","author":[{"given":"C\u00e9dric","family":"Josz","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0860-9913","authenticated-orcid":false,"given":"Jean Bernard","family":"Lasserre","sequence":"additional","affiliation":[]},{"given":"Bernard","family":"Mourrain","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,15]]},"reference":[{"issue":"2","key":"9672_CR1","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.acha.2014.03.004","volume":"38","author":"J-M Aza\u00efs","year":"2015","unstructured":"Aza\u00efs, J.-M., de Castro, Y., Gamboa, F.: Spike detection from inaccurate samplings. Appl. Comput. Harmon. Anal. 38(2), 177\u2013195 (2015)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9672_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 301\u2013309. ACM (1988)","DOI":"10.1145\/62212.62241"},{"issue":"2","key":"9672_CR3","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1109\/TIT.1968.1054109","volume":"14","author":"ER Berlekamp","year":"1968","unstructured":"Berlekamp, E.R.: Nonbinary BCH decoding. IEEE Trans. Inf. Theory 14(2), 242\u2013242 (1968)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9672_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.acha.2005.01.003","volume":"19","author":"G Beylkin","year":"2005","unstructured":"Beylkin, G., Monz\u00f3n, L.: On approximation of functions by exponential sums. Appl. Comput. Harmon. Anal. 19(1), 17\u201348 (2005)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9672_CR5","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/j.crma.2008.03.014","volume":"346","author":"EJ Cand\u00e8s","year":"2008","unstructured":"Cand\u00e8s, E.J.: The restricted isometry property and its implications for compressed sensing. C.R. Acad. Sci. Paris Ser. I 346, 589\u2013592 (2008)","journal-title":"C.R. Acad. Sci. Paris Ser. I"},{"issue":"6","key":"9672_CR6","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1007\/s00041-013-9292-3","volume":"19","author":"EJ Cand\u00e8s","year":"2013","unstructured":"Cand\u00e8s, E.J., Carlos, F.-G.: Super-resolution from noisy data. J. Fourier Anal. Appl. 19(6), 1229\u20131254 (2013)","journal-title":"J. Fourier Anal. Appl."},{"issue":"6","key":"9672_CR7","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1002\/cpa.21455","volume":"67","author":"EJ Cand\u00e8s","year":"2014","unstructured":"Cand\u00e8s, E.J., Fernandez-Granda, C.: Towards a mathematical theory of super-resolution. Commun. Pure Appl. Math. 67(6), 906\u2013956 (2014)","journal-title":"Commun. Pure Appl. Math."},{"issue":"11","key":"9672_CR8","doi-asserted-by":"publisher","first-page":"7235","DOI":"10.1109\/TIT.2011.2161794","volume":"57","author":"EJ Candes","year":"2011","unstructured":"Candes, E.J., Plan, Y.: A probabilistic and RIPless theory of compressed sensing. IEEE Trans. Inf. Theory 57(11), 7235\u20137254 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"9672_CR9","doi-asserted-by":"publisher","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"EJ Candes","year":"2006","unstructured":"Candes, E.J., Tao, T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406\u20135425 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"9672_CR10","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Cand\u00e8s","year":"2014","unstructured":"Cand\u00e8s, E.J., Tao, T.: Decoding by linear programming. IEEE Inform. Theory 51(12), 4203\u20134215 (2014). 2005","journal-title":"IEEE Inform. Theory"},{"issue":"8","key":"9672_CR11","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"key":"9672_CR12","first-page":"189","volume":"54","author":"RE Curto","year":"2005","unstructured":"Curto, R.E., Fialkow, L.A.: Truncated K-moment problems in several variables. J. Operator Theory 54, 189\u2013226 (2005)","journal-title":"J. Operator Theory"},{"key":"9672_CR13","first-page":"24","volume":"1","author":"GR Baron de Prony de","year":"1795","unstructured":"de Baron de Prony, G.R.: Essai exp\u00e9rimental et analytique: Sur les lois de la dilatabilit\u00e9 de fluides \u00e9lastique et sur celles de la force expansive de la vapeur de l\u2019alcool, \u00e0 diff\u00e9rentes temp\u00e9ratures. J. Ecole Polyt. 1, 24\u201376 (1795)","journal-title":"J. Ecole Polyt."},{"key":"9672_CR14","doi-asserted-by":"crossref","unstructured":"Cuyt, A., Lee, W.-S.: Sparse interpolation and rational approximation. In: Hardin, D., Lubinsky, D., Simanek, B., et al. (eds.) Contemporary Mathematics, vol. 661, pp 229\u2013242. American Mathematical Society, Providence (2016)","DOI":"10.1090\/conm\/661\/13284"},{"key":"9672_CR15","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1109\/TIT.2016.2619368","volume":"63","author":"Y Castro De","year":"2017","unstructured":"De Castro, Y., Gamboa, F., Henrion, D., Lasserre, J.-B.: Exact solutions to super-resolution on semi-algebraic domains in higher dimensions. IEEE Trans. Inform. Theory 63, 621\u2013630 (2017)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9672_CR16","volume-title":"Linear programming 1: Introduction","author":"GB Dantzig","year":"1997","unstructured":"Dantzig, G.B., Thapa, M.N.: Linear programming 1: Introduction. Springer-verlag New York Inc., New York (1997)"},{"issue":"5","key":"9672_CR17","doi-asserted-by":"publisher","first-page":"1315","DOI":"10.1007\/s10208-014-9228-6","volume":"15","author":"V Duval","year":"2015","unstructured":"Duval, V., Peyr\u00e9, G.: Exact support recovery for sparse spikes deconvolution. Found. Comput. Math. 15(5), 1315\u20131355 (2015)","journal-title":"Found. Comput. Math."},{"key":"9672_CR18","first-page":"194","volume":"4","author":"YY Fan","year":"2016","unstructured":"Fan, Y.Y., Kamath, C.: A comparison of compressed sensing and sparse recovery algorithms applied to simulation data. Stat. Optim. Inform. Computing 4, 194\u2013213 (2016)","journal-title":"Stat. Optim. Inform. Computing"},{"key":"9672_CR19","unstructured":"Filbir, F., Schr\u00f6der, K.: Exact recovery of discrete measures from Wigner D-moments. arXiv: 1606.05306 (2016)"},{"issue":"8","key":"9672_CR20","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1016\/j.jsc.2008.11.003","volume":"44","author":"M Giesbrecht","year":"2009","unstructured":"Giesbrecht, M., Labahn, G., Lee, W.-S.: Symbolic\u2013numeric sparse interpolation of multivariate polynomials. J. Symb. Comput. 44(8), 943\u2013959 (2009)","journal-title":"J. Symb. Comput."},{"issue":"2","key":"9672_CR21","doi-asserted-by":"publisher","first-page":"R1","DOI":"10.1088\/0266-5611\/19\/2\/201","volume":"19","author":"G Golub","year":"2003","unstructured":"Golub, G., Pereyra, V.: Separable nonlinear least squares: The variable projection method and its applications. Inverse Prob. 19(2), R1\u2013R26 (2003)","journal-title":"Inverse Prob."},{"issue":"6","key":"9672_CR22","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"DY Grigoriev","year":"1990","unstructured":"Grigoriev, D.Y., Karpinski, M., Singer, M.F.: Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comput. 19 (6), 1059\u20131063 (1990)","journal-title":"SIAM J. Comput."},{"key":"9672_CR23","doi-asserted-by":"crossref","unstructured":"Harmouch, J., Khalil, H., Mourrain, B.: Structured Low Rank Decomposition of Multivariate Hankel Matrices. Linear Algebra and its Applications (2017)","DOI":"10.1016\/j.laa.2017.04.015"},{"key":"9672_CR24","doi-asserted-by":"crossref","unstructured":"Hassanieh, Hitham, Indyk, Piotr, Katabi, Dina, Price, Eric: Nearly optimal sparse Fourier transform. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC \u201912, pp. 563\u2013578. ACM Press (2012)","DOI":"10.1145\/2213977.2214029"},{"key":"9672_CR25","unstructured":"Josz, C., Molzahn, D.K.: Large Scale Complex Polynomial Optimization. arXiv: 1508.02068"},{"key":"9672_CR26","doi-asserted-by":"crossref","unstructured":"Kaltofen, E., Lakshman, Y.N.: Sparse multivariate polynomial interpolation algorithms. In: Proceedings of the International Symposium ISSAC\u201988 on Symbolic and Algebraic Computation, ISSAC \u201988, pp 467\u2013474. Springer, London (1989)","DOI":"10.1007\/3-540-51084-2_44"},{"key":"9672_CR27","first-page":"130","volume-title":"Fast Estimates of Hankel Matrix Condition Numbers and Numeric Sparse Interpolation","author":"EL Kaltofen","year":"2011","unstructured":"Kaltofen, E.L., Lee, W.-S., Yang, Z.: Fast Estimates of Hankel Matrix Condition Numbers and Numeric Sparse Interpolation, pp 130\u2013136. ACM Press, New York (2011)"},{"key":"9672_CR28","volume-title":"Theory of Motion Control","author":"NN Krasovskii","year":"1968","unstructured":"Krasovskii, N.N.: Theory of Motion Control. Moscow, Nauka (1968). (in Russian)"},{"key":"9672_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.laa.2015.10.023","volume":"490","author":"S Kunis","year":"2016","unstructured":"Kunis, S., Peter, T., R\u00f6mer, T., von der Ohe, U.: A multivariate generalization of Prony\u2019s method. Linear Algebra Appl. 490, 31\u201347 (2016)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"9672_CR30","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00013-009-0007-6","volume":"93","author":"M Laurent","year":"2009","unstructured":"Laurent, M., Mourrain, B.: A generalized flat extension theorem for moment matrices. Arch. Math. 93(1), 87\u201398 (2009)","journal-title":"Arch. Math."},{"issue":"1","key":"9672_CR31","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","volume":"15","author":"J Massey","year":"1969","unstructured":"Massey, J.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122\u2013127 (1969)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"9672_CR32","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1007\/s10208-017-9372-x","volume":"18","author":"B Mourrain","year":"2018","unstructured":"Mourrain, B.: Polynomial-exponential decomposition from moments. Found. Comput. Math. 18(6), 1435\u20131492 (2018). https:\/\/doi.org\/10.1007\/s10208-017-9372-x","journal-title":"Found. Comput. Math."},{"issue":"1","key":"9672_CR33","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0302004","volume":"2","author":"LW Neustadt","year":"1964","unstructured":"Neustadt, L.W.: Optimization, a moment problem, and nonlinear programming. Journal of the Society for Industrial and Applied Mathematics Series A Control 2(1), 33\u201353 (1964)","journal-title":"Journal of the Society for Industrial and Applied Mathematics Series A Control"},{"issue":"1-2","key":"9672_CR34","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-013-0680-x","volume":"146","author":"J Nie","year":"2014","unstructured":"Nie, J.: Optimality conditions and finite convergence of Lasserre?s hierarchy. Math. Program. Ser Optimality A 146(1-2), 97\u2013121 (2014)","journal-title":"Math. Program. Ser Optimality A"},{"key":"9672_CR35","doi-asserted-by":"publisher","DOI":"10.2174\/97816080504821100101","volume-title":"Exponential Data Fitting and Its Applications","author":"V Pereyra","year":"2012","unstructured":"Pereyra, V., Scherer, G., et al.: Exponential Data Fitting and Its Applications. Bentham Science Publishers, Sharjah (2012)"},{"issue":"1","key":"9672_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/17M1147822","volume":"51","author":"C Poon","year":"2019","unstructured":"Poon, C., Peyr\u00e9, G.: Multi-dimensional sparse super-resolution. SIAM J. Math. Anal. 51(1), 1\u201344 (2019)","journal-title":"SIAM J. Math. Anal."},{"issue":"3-4","key":"9672_CR37","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1080\/00036810903569499","volume":"90","author":"D Potts","year":"2011","unstructured":"Potts, D., Tasche, M.: Nonlinear approximation by sums of nonincreasing exponentials. Appl. Anal. 90(3-4), 609\u2013626 (2011)","journal-title":"Appl. Anal."},{"issue":"7","key":"9672_CR38","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1109\/29.32276","volume":"37","author":"R Richard","year":"1989","unstructured":"Richard, R., Kailath, T.: ESPRIT-Estimation of signal parameters via rotational invariance techniques. IEEE Trans. Acoust. Speech Signal Process. 37(7), 984\u2013995 (1989)","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"key":"9672_CR39","volume-title":"Real and Complex Analysis","author":"W Rudin","year":"1986","unstructured":"Rudin, W.: Real and Complex Analysis. McGraw-Hill Education, New York (1986)"},{"issue":"2","key":"9672_CR40","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00211-016-0844-8","volume":"136","author":"T Sauer","year":"2017","unstructured":"Sauer, T.: Prony\u2019s method in several variables. Numer. Math. 136(2), 411\u2013438 (2017). https:\/\/doi.org\/10.1007\/s00211-016-0844-8","journal-title":"Numer. Math."},{"key":"9672_CR41","volume-title":"Spectral Analysis of Signals","author":"P Stoica","year":"2005","unstructured":"Stoica, P., Moses, R.L.: Spectral Analysis of Signals. Pearson\/prentice Hall, Upper Saddle River (2005)"},{"issue":"7","key":"9672_CR42","doi-asserted-by":"publisher","first-page":"1758","DOI":"10.1109\/78.143447","volume":"40","author":"A Lee Swindlehurst","year":"1992","unstructured":"Lee Swindlehurst, A., Kailath, T.: A performance analysis of subspace-based methods in the presence of model errors. I. The MUSIC algorithm. IEEE Trans. Signal Process. 40(7), 1758\u20131774 (1992)","journal-title":"IEEE Trans. Signal Process."},{"key":"9672_CR43","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM \u201979, pp 216\u2013226. Springer, London (1979)","DOI":"10.1007\/3-540-09519-5_73"},{"issue":"3","key":"9672_CR44","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"R Zippel","year":"1990","unstructured":"Zippel, R.: Interpolating polynomials from their values. J. Symb. Comput. 9 (3), 375\u2013403 (1990)","journal-title":"J. Symb. Comput."},{"key":"9672_CR45","volume-title":"Hankel and Toeplitz Matrices and Forms: Algebraic Theory","author":"IS Iohvidov","year":"1982","unstructured":"Iohvidov, I.S.: Hankel and Toeplitz Matrices and Forms: Algebraic Theory. Birkh\u00e4user Verlag, Boston (1982)"},{"key":"9672_CR46","doi-asserted-by":"crossref","unstructured":"Comer, M.T., Kaltofen, E.L., Pernet, C.: Sparse polynomial interpolation and Berlekamp\/Massey algorithms that correct outlier errors in input values. In: Proceedings of the Sparse Polynomial International Symposium on Symbolic and Algebraic Computation, ISSAC \u201912, pp. 138\u2013145. Grenoble, France. 2012 (2012)","DOI":"10.1145\/2442829.2442852"}],"container-title":["Advances in Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-019-09672-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10444-019-09672-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10444-019-09672-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T21:54:56Z","timestamp":1663106096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10444-019-09672-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,15]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["9672"],"URL":"https:\/\/doi.org\/10.1007\/s10444-019-09672-2","relation":{},"ISSN":["1019-7168","1572-9044"],"issn-type":[{"type":"print","value":"1019-7168"},{"type":"electronic","value":"1572-9044"}],"subject":[],"published":{"date-parts":[[2019,3,15]]},"assertion":[{"value":"18 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}