Library / Geometry of Error Amplification in Solving the Prony System with near-colliding Nodes


Reference

Andrey Akinshin, Gil Goldman, Yosef Yomdin “Geometry of error amplification in solving the Prony system with near-colliding nodes” (2021) // Mathematics of Computation. Vol. 90. No 327. Pp. 267–302. DOI: 10.1090/mcom/3571

Abstract

We consider a reconstruction problem for “spike-train” sig nals F of the a priori known form F ( x ) = ∑ d j =1 a j $\delta$ ( x − x j ) , from their moments m k ( F ) = ∫ x k F ( x ) dx. We assume m k ( F ) to be known for k = 0 , 1 , . . . , 2 d − 1 , with an absolute error not exceeding ǫ \textgreater 0. This problem is essentially equivalent to solving the Prony system ∑ d j =1 a j x k j = m k ( F ) , k = 0 , 1 , . . . , 2 d − 1 . We study the “geometry of error amplification” in reconstruc tion of F from m k ( F ) , in situations where the nodes x 1 , . . . , x d near-collide, i.e. form a cluster of size h ≪ 1. We show that in this case error amplification is governed by the “Prony leaves” S q F, in the parameter space of signals F , along which the first q + 1 moments remain constant. On this base we produce accurate , up to the constants, lower and upper bounds on the worst case r econstruction error, and show how the Prony leaves can help in improving rec onstruction accuracy.

Bib

@Article{akinshin2021mathcomp,
  abstract = {We consider a reconstruction problem for “spike-train” sig nals F of the a priori known form F ( x ) = ∑ d j =1 a j $\delta$ ( x − x j ) , from their moments m k ( F ) = ∫ x k F ( x ) dx. We assume m k ( F ) to be known for k = 0 , 1 , . . . , 2 d − 1 , with an absolute error not exceeding ǫ \textgreater 0. This problem is essentially equivalent to solving the Prony system ∑ d j =1 a j x k j = m k ( F ) , k = 0 , 1 , . . . , 2 d − 1 . We study the “geometry of error amplification” in reconstruc tion of F from m k ( F ) , in situations where the nodes x 1 , . . . , x d near-collide, i.e. form a cluster of size h ≪ 1. We show that in this case error amplification is governed by the “Prony leaves” S q F, in the parameter space of signals F , along which the first q + 1 moments remain constant. On this base we produce accurate , up to the constants, lower and upper bounds on the worst case r econstruction error, and show how the Prony leaves can help in improving rec onstruction accuracy.},
  author = {Akinshin, Andrey and Goldman, Gil and Yomdin, Yosef},
  journal = {Mathematics of Computation},
  volume = {90},
  number = {327},
  pages = {267--302},
  year = {2021},
  language = {english},
  title = {Geometry of error amplification in solving the Prony system with near-colliding nodes},
  url = {https://publons.com/publon/39312469/},
  doi = {10.1090/mcom/3571},
  custom-project = {signal-processing},
  custom-tags = {WoS,Scopus},
  custom-url-arxiv = {https://arxiv.org/abs/1701.04058}
}