Motivated by recent work on atomic norms in inverse problems, we propose a new approach to line spectral estimation that provides theoretical guarantees for the mean-squared-error (MSE) performance in the presence of noise and without knowledge of the model order. We propose an abstract theory of denoising with atomic norms and specialize this theory to provide a convex optimization problem for estimating the frequencies and phases of a mixture of complex exponentials. We show that the associated convex optimization problem can be solved in polynomial time via semidefinite programming (SDP). We also show that the SDP can be approximated by an l1-regularized least-squares problem that achieves nearly the same error rate as the SDP but can scale to much larger problems. We compare both SDP and l1-based approaches with classical line spectral analysis methods and demonstrate that the SDP outperforms the l1 optimization which outperforms MUSIC, Cadzow's, and Matrix Pencil approaches in terms of MSE over a wide range of signal-to-noise ratios.
@cite_33: Abstract Modifications of Prony's classical technique for estimating rate constants in exponential fitting problems have many contemporary applications. In this article the consistency of Prony's method and of related algorithms based on maximum likelihood is discussed as the number of observations n → ∞ by considering the simplest possible models for fitting sums of exponentials to observed data. Two sampling regimes are relevant, corresponding to transient problems and problems of frequency estimation, each of which is associated with rather different kinds of behavior. The general pattern is that the stronger results are obtained for the frequency estimation problem. However, the algorithms considered are all scaling dependent and consistency is not automatic. A new feature that emerges is the importance of an appropriate choice of scale in order to ensure consistency of the estimates in certain cases. The tentative conclusion is that algorithms referred to as Objective function Reweighting Algorithms ...
@cite_9: 
@cite_42: High-resolution signal parameter estimation is a problem of significance in many signal processing applications. Such applications indude direction-of-arrival estimation, system identification, and time series analysis. A novel approach to the general problem of signal parameter estimation is described. Although discussed in the context of directionof- arrival estimation, ESPRIT can be applied to a wide variety of problems. It exploits an underlying rotational invariance among signal subspaces induced by an array of sensors with a translational invariance structure. The technique, when applicable, manifests significant performance and computational advantages over previous algorithms such as Burg's maximum entropy method, Capon's maximum likelihood method, and Schmidt's multiple signal classification.
@cite_47: Processing the signals received on an array of sensors for the location of the emitter is of great enough interest to have been treated under many special case assumptions. The general problem considers sensors with arbitrary locations and arbitrary directional characteristics (gain phase polarization) in a noise interference environment of arbitrary covariance matrix. This report is concerned first with the multiple emitter aspect of this problem and second with the generality of solution. A description is given of the multiple signal classification (MUSIC) algorithm, which provides asymptotically unbiased estimates of 1) number of incident wavefronts present; 2) directions of arrival (DOA) (or emitter locations); 3) strengths and cross correlations among the incident waveforms; 4) noise interference strength. Examples and comparisons with methods based on maximum likelihood (ML) and maximum entropy (ME), as well as conventional beamforming are included. An example of its use as a multiple frequency estimator operating on time series is included.
@cite_10: A study of a matrix pencil method for estimating frequencies and damping factors of exponentially damped and or undamped sinusoids in noise is presented. Comparison of this method to a polynomial method (SVD-Prony method) shows that the matrix pencil method and the polynomial method are two special cases of a matrix prediction approach and that the pencil method is more efficient in computation and less restrictive about signal probes. It is found through perturbation analysis and simulation that, for signals with unknown damping factors, the pencil method is less sensitive to noise than the polynomial method. An expression of the Cramer-Rao bound for the exponential signals is presented. >
The classical methods of line spectral estimation, often called linear prediction methods, are built upon the seminal interpolation method of Prony @cite_9 . In the noiseless case, with as little as @math measurements, Prony's technique can identify the frequencies exactly, no matter how close the frequencies are. However, Prony's technique is known to be sensitive to noise due to instability of polynomial rooting @cite_33 . Following Prony, several methods have been employed to robustify polynomial rooting method including the Matrix Pencil algorithm @cite_10 , which recasts the polynomial rooting as a generalized eigenvalue problem and cleverly uses extra observations to guard against noise. The MUSIC @cite_47 and ESPRIT @cite_42 algorithms exploit the low rank structure of the autocorrelation matrix.