Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 65H10, 94A12
  • Retrieve articles in all journals with MSC (2010): 65H10, 94A12
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