Back to Search Start Over

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

Authors :
Akinshin, Andrey
Goldman, Gil
Yomdin, Yosef
Source :
Mathematics of Computation; Jan2021, Vol. 90 Issue 327, p267-302, 36p
Publication Year :
2021

Abstract

We consider a reconstruction problem for ''spike-train'' signals F of an a priori known form F(x) = ∑<subscript>j = 1</subscript><superscript>d</superscript>a<subscript>j</subscript>δ(x−x<subscript>j</subscript>), from their moments m<subscript>k</subscript>(F) = ∫ x<superscript>k</superscript>F(x)dx. We assume that the moments m<subscript>k</subscript>(F), k = 0,1, . . . ,2d−1, are known with an absolute error not exceeding ε > 0. This problem is essentially equivalent to solving the Prony system ∑<subscript>j = 1</subscript><superscript>d</superscript> a<subscript>j</subscript>x<subscript>j</subscript><superscript>k</superscript> = m<subscript>k</subscript>(F), k = 0,1, . . . ,2d−1. We study the ''geometry of error amplification'' in reconstruction of F from m<subscript>k</subscript>(F), in situations where the nodes x<subscript>1</subscript>, . . . ,x<subscript>d</subscript> near-collide, i.e., form a cluster of size h << 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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00255718
Volume :
90
Issue :
327
Database :
Complementary Index
Journal :
Mathematics of Computation
Publication Type :
Academic Journal
Accession number :
146637479
Full Text :
https://doi.org/10.1090/mcom/3571