Non-negative super-resolution is stable

Conference item

We consider the problem of localizing point sources on an interval from possibly noisy measurements. In the absence of noise, we show that measurements from Chebyshev systems are an injective map for non-negative sparse measures, and therefore non-negativity is sufficient to ensure uniqueness for sparse measures. Moreover, we characterize nonnegative solutions from inexact measurements and show that any non-negative solution consistent with the measurements is proportionally close to the solution of the system with exact measurements. Our results substantially simplify, extend, and generalize the prior work by De Castro et al. and Schiebinger et al., which relies upon sparsifying penalties, by showing that it is the non-negativity constraint, rather than any particular algorithm, that imposes uniqueness of the sparse non-negative measure, and by extending the results to inexact samples.

Authors: Eftekhari, A; Tanner, J; Thompson, A; Toader, B; Tyagi, H

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Institute of Electrical and Electronics Engineers
• Host title: IEEE Data Science Workshop 2018
• Journal: IEEE Data Science Workshop 2018
• Publication date: 2018-08-20
• Acceptance date: 2018-04-26
• DOI: 10.1109/DSW.2018.8439120
• Keywords: super-resolution; feasibility programs; Chebyshev systems; non-negative sparse measures