Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Geometry of error amplification in solving the Prony system with near-colliding nodes


Authors: Andrey Akinshin, Gil Goldman and Yosef Yomdin
Journal: Math. Comp. 90 (2021), 267-302
MSC (2010): Primary 65H10, 94A12
DOI: https://doi.org/10.1090/mcom/3571
Published electronically: September 9, 2020
MathSciNet review: 4166461
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


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
Email: andrey.akinshin@gmail.com

Gil Goldman
Affiliation: Department of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel
MR Author ID: 1233252
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

DOI: https://doi.org/10.1090/mcom/3571
Keywords: Signal reconstruction, spike-trains, Fourier transform, Prony systems, sparsity.
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.
Article copyright: © Copyright 2020 American Mathematical Society