Error amplification in solving Prony system with near-colliding nodes

Andrey Akinshin, Dmitry Batenkov, Gil Goldman, Yosef Yomdin

Abstract

We consider a reconstruction problem for spike-train signals $F$ of the 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 $m_k(F)$ to be known for $k=0,1,\ldots,2d-1,$ with an absolute error not exceeding $\epsilon > 0$. This problem is essentially equivalent to solving the system $\sum_{j=1}^d a_jx_j^k=m_k(F), k=0,1,\ldots,2d-1.$ We study the geometry of error 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 the Prony $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 reconstruction error, and show how the leaves can help in improving reconstruction accuracy.

Introduction

The Prony system is a classic mathematical problem: reconstructing a "spike-train" signal—a sum of discrete Dirac deltas—from its moments. This task is fundamental to fields such as radar, microscopy, and spectroscopy. However, the problem becomes notoriously ill-posed in the "super-resolution" regime, where spikes are closely packed in a cluster of size $h \ll 1$. In such cases, tiny measurement errors $\epsilon$ can lead to massive errors in the estimated positions (nodes) and heights (amplitudes) of the spikes. This paper investigates the exact geometry of this error amplification to provide rigorous bounds and improved reconstruction techniques.

Methodology

The authors analyze the error by mapping signals into a normalized "model space," where clusters are centered at the origin with unit width. This normalization isolates the intrinsic properties of the error from the absolute scale.

A central concept introduced is the Prony Variety ($S_q$), an algebraic variety defined by the set of signals whose first $q$ moments are identical. These varieties serve as the "skeleton" of the error set. By applying a quantitative version of the Inverse Function Theorem, the authors bound the Jacobian of the mapping from moments to signal parameters.

Finally, they propose the Prony Curve Reconstruction Procedure (PCRP). This algorithm leverages the geometric structure of the Prony varieties to "snap" noisy estimates back toward the feasible region, significantly enhancing reconstruction accuracy compared to standard methods.

The Geometry of Error

A key finding is that the error set—the collection of all signals consistent with noisy measurements—is not a random cloud. Instead, it forms a "deformed parallelepiped" that is highly elongated along specific Prony varieties.

Visualization of the error set $\bar{E}_\epsilon(F)$ and the Prony variety $S_2(G)$ in the parameter space. The error is highly structured and stretched along the algebraic curve.

As shown in the figure above, the error set $\bar{E}_\epsilon(F)$ is constrained by the geometry of the variety $S_2(G)$. This structure implies a hierarchy of accuracy: while individual spike parameters may be highly uncertain, the signal's projection onto lower-order Prony varieties remains relatively stable. Specifically, the variety $S_q$ can be reconstructed with an accuracy of $O(\epsilon h^{-q})$, which is significantly better than the point-wise reconstruction of the full signal.

Key Results and Bounds

The study provides tight mathematical bounds on the worst-case reconstruction error for a cluster of $d$ nodes:

  • Amplitudes and Total Signal: Error scales as $O(\epsilon h^{-2d+1})$.
  • Node Positions: Error scales as $O(\epsilon h^{-2d+2})$.

The error amplification is dominated by the cluster size $h$, with the uncertainty volume exploding at a polynomial rate as $h \to 0$. Numerical experiments confirm that as $h$ decreases, the error set converges onto the Prony variety $S_{2d-2}$. Furthermore, the PCRP algorithm demonstrates superior performance, achieving errors of order $h^2$ in scenarios where standard solutions (SRP) only achieve order $h$ for the same noise level.

Conclusion and Future Directions

This work characterizes the algebraic "skeleton" of error in the Prony system, transforming a purely numerical problem into a geometric one. By understanding how error is distributed along Prony varieties, researchers can use a priori constraints to navigate the error set and achieve higher resolution.

Future work will focus on extending these geometric proofs to signals with multiple clusters and exploring the "large noise" regime where the system encounters geometric singularities. Additionally, improving the computational efficiency of constructing these high-dimensional algebraic varieties remains a key challenge for real-time applications.

Summary updated

Abstract

We consider a reconstruction problem for spike-train signals $F$ of the 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 $m_k(F)$ to be known for $k=0,1,\ldots,2d-1,$ with an absolute error not exceeding $\epsilon > 0$. This problem is essentially equivalent to solving the system $\sum_{j=1}^d a_jx_j^k=m_k(F), k=0,1,\ldots,2d-1.$ We study the geometry of error 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 the Prony $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 reconstruction error, and show how the leaves can help in improving reconstruction accuracy.
BibTeX
@article{akinshin2021error,
  author = {Andrey Akinshin and Dmitry Batenkov and Gil Goldman and Yosef Yomdin},
  title = {{Error amplification in solving Prony system with near-colliding nodes}},
  journal = {Math. Comput},
  year = {2021},
  doi = {10.1090/mcom/3571},
}
Figure