Search

In this paper we establish accuracy bounds of Prony's method (PM) for recovery of sparse measures from incomplete and noisy frequency measurements, or the so-called problem of super-resolution, when the minimal separation between the points in the support of the measure may be much smaller than the Rayleigh limit. In particular, we show that PM is optimal with respect to the previously established min-max bound for the problem, in the setting when the measurement bandwidth is constant, with the minimal separation going to zero. Our main technical contribution is an accurate analysis of the inter-relations between the different errors in each step of PM, resulting in previously unnoticed cancellations. We also prove that PM is numerically stable in finite-precision arithmetic. We believe our analysis will pave the way to providing accurate analysis of known algorithms for the super-resolution problem in full generality., Comment: 30 pages, 15 figures

Inverse source problems are central to many applications in acoustics, geophysics, non-destructive testing, and more. Traditional imaging methods suffer from the resolution limit, preventing distinction of sources separated by less than the emitted wavelength. In this work we propose a method based on physically-informed neural-networks for solving the source refocusing problem, constructing a novel loss term which promotes super-resolving capabilities of the network and is based on the physics of wave propagation. We demonstrate the approach in the setup of imaging an a-priori unknown number of point sources in a two-dimensional rectangular waveguide from measurements of wavefield recordings along a vertical cross-section. The results show the ability of the method to approximate the locations of sources with high accuracy, even when placed close to each other.

We study recovery of amplitudes and nodes of a finite impulse train from noisy frequency samples. This problem is known as super-resolution under sparsity constraints and has numerous applications. An especially challenging scenario occurs when the separation between Dirac pulses is smaller than the Nyquist-Shannon-Rayleigh limit. Despite large volumes of research and well-established worst-case recovery bounds, there is currently no known computationally efficient method which achieves these bounds in practice. In this work we combine the well-known Prony's method for exponential fitting with a recently established decimation technique for analyzing the super-resolution problem in the above mentioned regime. We show that our approach attains optimal asymptotic stability in the presence of noise, and has lower computational complexity than the current state of the art methods., Comment: 5 pages, 10 figures

We consider the problem of stable recovery of sparse signals of the form $$F(x)=\sum_{j=1}^d a_j\delta(x-x_j),\quad x_j\in\mathbb{R},\;a_j\in\mathbb{C}, $$ from their spectral measurements, known in a bandwidth $\Omega$ with absolute error not exceeding $\epsilon>0$. We consider the case when at most $p\le d$ nodes $\{x_j\}$ of $F$ form a cluster whose extent is smaller than the Rayleigh limit ${1\over\Omega}$, while the rest of the nodes are well separated. Provided that $\epsilon \lessapprox SRF^{-2p+1}$, where $SRF=(\Omega\Delta)^{-1}$ and $\Delta$ is the minimal separation between the nodes, we show that the minimax error rate for reconstruction of the cluster nodes is of order ${1\over\Omega}SRF^{2p-1}\epsilon$, while for recovering the corresponding amplitudes $\{a_j\}$ the rate is of the order $SRF^{2p-1}\epsilon$. Moreover, the corresponding minimax rates for the recovery of the non-clustered nodes and amplitudes are ${\epsilon\over\Omega}$ and $\epsilon$, respectively. These results suggest that stable super-resolution is possible in much more general situations than previously thought. Our numerical experiments show that the well-known Matrix Pencil method achieves the above accuracy bounds.

We provide an overview of some results on the "geometry of error amplification" in solving Prony system, in situations where the nodes near-collide. It turns out to be governed by the "Prony foliations" $S_q$, whose leaves are "equi-moment surfaces" in the parameter space. Next, we prove some new results concerning explicit parametrization of the Prony leaves.

We consider the problem of reconstruction of planar domains from their moments. Specifically, we consider domains with boundary which can be represented by a union of a finite number of pieces whose graphs are solutions of a linear differential equation with polynomial coefficients. This includes domains with piecewise-algebraic and, in particular, piecewise-polynomial boundaries. Our approach is based on one-dimensional reconstruction method of [Bat]* and a kind of "separation of variables" which reduces the planar problem to two one-dimensional problems, one of them parametric. Several explicit examples of reconstruction are given. Another main topic of the paper concerns "invisible sets" for various types of incomplete moment measurements. We suggest a certain point of view which stresses remarkable similarity between several apparently unrelated problems. In particular, we discuss zero quadrature domains (invisible for harmonic polynomials), invisibility for powers of a given polynomial, and invisibility for complex moments (Wermer's theorem and further developments). The common property we would like to stress is a "rigidity" and symmetry of the invisible objects. * D.Batenkov, Moment inversion of piecewise D-finite functions, Inverse Problems 25 (2009) 105001, Proceedings of Complex Analysis and Dynamical Systems V, 2012

We consider the problem of ``algebraic reconstruction'' of linear combinations of shifts of several signals $f_1,\ldots,f_k$ from the Fourier samples. For each $r=1,\ldots,k$ we choose sampling set $S_r$ to be a subset of the common set of zeroes of the Fourier transforms ${\cal F}(f_\l), \ \l \ne r$, on which ${\cal F}(f_r)\ne 0$. We show that in this way the reconstruction system is reduced to $k$ separate systems, each including only one of the signals $f_r$. Each of the resulting systems is of a ``generalized Prony'' form. We discuss the problem of unique solvability of such systems, and provide some examples.

We consider "Taylor domination" property for an analytic function $f(z)=\sum_{k=0}^{\infty}a_{k}z^{k},$ in the complex disk $D_R$, which is an inequality of the form \[ |a_{k}|R^{k}\leq C\ \max_{i=0,\dots,N}\ |a_{i}|R^{i}, \ k \geq N+1. \] This property is closely related to the classical notion of "valency" of $f$ in $D_R$. For $f$ - rational function we show that Taylor domination is essentially equivalent to a well-known and widely used Tur��n's inequality on the sums of powers. Next we consider linear recurrence relations of the Poincar�� type \[ a_{k}=\sum_{j=1}^{d}[c_{j}+��_{j}(k)]a_{k-j},\ \ k=d,d+1,\dots,\quad\text{with }\lim_{k\rightarrow\infty}��_{j}(k)=0. \] We show that the generating functions of their solutions possess Taylor domination with explicitly specified parameters. As the main example we consider moment generating functions, i.e. the Stieltjes transforms \[ S_{g}\left(z\right)=\int\frac{g\left(x\right)dx}{1-zx}. \] We show Taylor domination property for such $S_{g}$ when $g$ is a piecewise D-finite function, satisfying on each continuity segment a linear ODE with polynomial coefficients.

We consider the "moment vanishing problem" for a general class of piecewise-analytic functions which satisfy on each continuity interval a linear ODE with polynomial coefficients. This problem, which essentially asks how many zero first moments can such a (nonzero) function have, turns out to be related to several difficult questions in analytic theory of ODEs (Poincare's Center-Focus problem) as well as in Approximation Theory and Signal Processing ("Algebraic Sampling"). While the solution space of any particular ODE admits such a bound, it will in the most general situation depend on the coefficients of this ODE. We believe that a good understanding of this dependence may provide a clue for attacking the problems mentioned above. In this paper we undertake an approach to the moment vanishing problem which utilizes the fact that the moment sequences under consideration satisfy a recurrence relation of fixed length, whose coefficients are polynomials in the index. For any given operator, we prove a general bound for its moment vanishing index. We also provide uniform bounds for several operator families.

Systems of Prony type appear in various signal reconstruction problems such as finite rate of innovation, superresolution and Fourier inversion of piecewise smooth functions. We propose a novel approach for solving Prony-type systems, which requires sampling the signal at arithmetic progressions. By keeping the number of equations small and fixed, we demonstrate that such "decimation" can lead to practical improvements in the reconstruction accuracy. As an application, we provide a solution to the so-called Eckhoff's conjecture, which asked for reconstructing jump positions and magnitudes of a piecewise-smooth function from its Fourier coefficients with maximal possible asymptotic accuracy -- thus eliminating the Gibbs phenomenon.

This paper presents some results on a well-known problem in Algebraic Signal Sampling and in other areas of applied mathematics: reconstruction of piecewise-smooth functions from their integral measurements (like moments, Fourier coefficients, Radon transform, etc.). Our results concern reconstruction (from the moments or Fourier coefficients) of signals in two specific classes: linear combinations of shifts of a given function, and "piecewise $D$-finite functions" which satisfy on each continuity interval a linear differential equation with polynomial coefficients. In each case the problem is reduced to a solution of a certain type of non-linear algebraic system of equations ("Prony-type system"). We recall some known methods for explicitly solving such systems in one variable, and provide extensions to some multi-dimensional cases. Finally, we investigate the local stability of solving the Prony-type systems.