We consider the problem of stable recovery of sparse signals of the form @math from their spectral measurements, known in a bandwidth @math with absolute error not exceeding @math . We consider the case when at most @math nodes @math of @math form a cluster of size @math , while the rest of the nodes are well separated. Provided that @math , we show that the minimax error rate for reconstruction of the cluster nodes is of order @math , while for recovering the corresponding amplitudes @math the rate is of the order @math . Moreover, the corresponding minimax rates for the recovery of the non-clustered nodes and amplitudes are @math and @math , respectively. Our numerical experiments show that the well-known Matrix Pencil method achieves the above accuracy bounds. These results suggest that stable super-resolution is possible in much more general situations than previously thought, and have implications for analyzing stability of super-resolution algorithms in this regime.
Available studies of certain high-resolution algorithms such as MUSIC @cite_32 , ESPRIT Matrix Pencil @cite_13 , Approximate Prony Method @cite_2 and others do not provide rigorous performance guarantees in the case @math . Our numerical experiments suggest that the Matrix Pencil is optimal in the high @math regime, and we hope that our proof techniques may be used in deriving the stability limits of these and other methods in the super-resolution regime. The special case of a single cluster can be solved with optimal accuracy by polynomial homotopy methods, as described in @cite_12 , however in order to generalize this algorithm to configurations with non-cluster nodes, we need to know the optimal decimation parameter @math .
@cite_13 @cite_32 @cite_12 @cite_2
2508934708 2963746586 2963604884 1978356474
In this paper Estimation of Signal Parameters via Rotational Invariance Techniques (ESPRIT) is developed for spectral estimation with single-snapshot measurement. Stability and resolution analysis with performance guarantee for Single-Snapshot ESPRIT (SS-ESPRIT) is the main focus. In the noise-free case, exact reconstruction is guaranteed for any arbitrary set of frequencies as long as the number of measurement data is at least twice the number of distinct frequencies to be recovered. In the presence of noise and under the assumption that the true frequencies are separated by at least two times Rayleigh's Resolution Length, an explicit error bound for frequency reconstruction is given in terms of the dynamic range and the separation of the frequencies. The separation and sparsity constraint compares favorably with those of the leading approaches to compressed sensing in the continuum. Abstract This paper studies the problem of line spectral estimation in the continuum of a bounded interval with one snapshot of array measurement. The single-snapshot measurement data are turned into a Hankel data matrix which admits the Vandermonde decomposition and is suitable for the MUSIC algorithm. The MUSIC algorithm amounts to finding the null space (the noise space) of the adjoint of the Hankel matrix, forming the noise-space correlation function and identifying the s smallest local minima of the noise-space correlation as the frequency set. In the noise-free case exact reconstruction is guaranteed for any arbitrary set of frequencies as long as the number of measurement data is at least twice the number of distinct frequencies to be recovered. In the presence of noise the stability analysis shows that the perturbation of the noise-space correlation is proportional to the spectral norm of the noise matrix as long as the latter is smaller than the smallest (nonzero) singular value of the noiseless Hankel data matrix. Under the assumption that the true frequencies are separated by at least twice the Rayleigh Length (RL), the stability of the noise-space correlation is proved by means of novel discrete Ingham inequalities which provide bounds on the largest and smallest nonzero singular values of the noiseless Hankel data matrix. The numerical performance of MUSIC is tested in comparison with other algorithms such as BLO-OMP and SDP (TV-min). While BLO-OMP is the stablest algorithm for frequencies separated above 4 RL, MUSIC becomes the best performing one for frequencies separated between 2 RL and 3 RL. Also, MUSIC is more efficient than other methods. MUSIC truly shines when the frequency separation drops to 1 RL or below when all other methods fail. Indeed, the resolution length of MUSIC decreases to zero as noise decreases to zero as a power law with an exponent smaller than an upper bound established by Donoho. Abstract We consider polynomial systems of Prony type, appearing in many areas of mathematics. Their robust numerical solution is considered to be difficult, especially in “near-colliding” situations. We consider a case when the structure of the system is a-priori fixed. We transform the nonlinear part of the Prony system into a Hankel-type polynomial system. Combining this representation with a recently discovered “decimation” technique, we present an algorithm which applies homotopy continuation to an appropriately chosen Hankel-type system as above. In this way, we are able to solve for the nonlinear variables of the original system with high accuracy when the data is perturbed. The recovery of signal parameters from noisy sampled data is a fundamental problem in digital signal processing. In this paper, we consider the following spectral analysis problem: Let f be a real-valued sum of complex exponentials. Determine all parameters of f, i.e., all different frequencies, all coefficients, and the number of exponentials from finitely many equispaced sampled data of f. This is a nonlinear inverse problem. In this paper, we present new results on an approximate Prony method (APM) which is based on [1]. In contrast to [1], we apply matrix perturbation theory such that we can describe the properties and the numerical behavior of the APM in detail. The number of sampled data acts as regularization parameter. The first part of APM estimates the frequencies and the second part solves an overdetermined linear Vandermonde-type system in a stable way. We compare the first part of APM also with the known ESPRIT method. The second part is related to the nonequispaced fast Fourier transform (NFFT). Numerical experiments show the performance of our method.