On robustness of ℓ1-regularization methods for spectral estimation

The use of ℓ₁-regularization in sparse estimation methods has received huge attention during the last decade, and applications in virtually all fields of applied mathematics have benefited greatly. This interest was sparked by the recovery results of Candès, Donoho, Tao, Tropp, et al. and has resulted in a framework for solving a set of combinatorial problems in polynomial time by using convex relaxation techniques. In this work we study the use of ℓ₁-regularization methods for high-resolution spectral estimation. In this problem, the dictionary is typically coherent and existing theory for robust/exact recovery does not apply. In fact, the robustness cannot be guaranteed in the usual strong sense. Instead, we consider metrics inspired by the Monge-Kantorovich transportation problem and show that the magnitude can be robustly recovered if the original signal is sufficiently sparse and separated. We derive both worst case error bounds as well as error bounds based on assumptions on the noise distribution.