Numerical stability bounds for algebraic systems of Prony type and their accurate solution by decimation
Dmitry Batenkov · arXiv (Cornell University) · 2014
The Prony system of equations and its higher-order (confluent) generalizations appear prominently in many theoretical and applied problems. For instance, in signal processing these systems arise in recovery of sums of Diracs from a finite number of their Fourier measurements. The accurate and robust numerical solution of Prony type systems is considered to be a challenging problem, in particular reconstructing closely spaced nonlinear parameters (``nodes'', e.g. the support of the Diracs) in the presence of perturbed data. Our first contribution is providing component-wise asymptotic estimates for the numerical condition of the high-order Prony system, when the number of equations can in general be greater than the number of unknowns. These results provide, in particular, an absolute resolution limit for any method whatsoever. Our second contribution is proposing a technique for the overdetermined Prony problem with closely spaced nodes by ``decimation'', i.e. taking subsets of the equations with indices belonging to arithmetic progressions, and subsequently solving the resulting square systems. We show that solution of a decimated system is as accurate as the solution to the full overdetermined problem. Thus, decimation provides a tool to achieve near-optimal super-resolution.