Stability and perturbation analysis of non-negative super-resolution

Thesis

The convolution of a discrete measure, x = P^k_i=1 a_iδ_ti , with a local window function, φ(s − t), is a common model for a measurement device whose resolution is substantially lower than that of the objects being observed. Super-resolution concerns localising the point sources {a_i , t_i} k i=1 with an accuracy beyond the essential support of φ(s−t), typically from m samples y(s_j) = P^k_i=1 a_iφ(s_j − t_i) + w_j , where w_j indicates an inexactness in the sample value. We consider the setting of x being non-negative and study two aspects of this problem: stability of the solutions with respect to measurement noise and perturbation of the solutions with respect to inaccuracies in the dual variable when solving the dual problem.

In Part I, we characterise non-negative solutions xˆ consistent with the samples within the bound ∥w∥₂ ≤ δ. We show that the integrals of xˆ and x over (t_i − E, t_i + E) are close, converging to one another as E and δ approach zero. We then show how to make this general result, for windows that form a Chebyshev system, precise for the case of φ(s − t) being a Gaussian window, in which case the average error between xˆ and x is O(δ ^1/6 ). The main innovation of this result is that non-negativity alone is sufficient to localise point sources beyond the sensor resolution and that, while regularisers such as total variation might be particularly effective, they are not required in the non-negative setting.

A practical approach for solving the problem is to consider its dual. In Part II, we study the stability of solutions with respect to the solutions to the dual problem. In particular, we establish a relationship between perturbations in the primal variable and perturbations the dual variable around the optimiser. We then establish a similar relationship between perturbations in the dual variable around the optimiser and the magnitude of the additive noise ∥w∥₂ in the measurements.

Authors: Toader, B

• DOI: 10.5287/ora-yq8qbdnmj
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: dual certificate; super-resolution; non-negative measures
• Subjects: Algebras, Linear--Data processing; Applied mathematics