Objectives

For non-Gaussian noise models such as impulsive noise, L¹ data fitting is more appropriate than standard L² terms, but leads to non-differentiable functionals to be minimized. The goal is to develop superlinearly convergent numerical methods for such inverse problems, including the automatic choice of regularization parameters.

Applications

Noise models of impulse type, e.g. salt-and-pepper or random-valued noise, arise in measurements because of malfunctioning pixels in camera sensors, faulty memory locations in hardware, or transmission in noisy channels. The advantage of using the L¹ norm is given by the fact that the solution is more robust with respect to outliers when compared to the L² norm.

Problem formulation and methods used

We consider for a bounded linear operator K :L² → L², noisy data y^δ ∈ L²(Ω) and α > 0 the minimization problem

()

Using Fenchel duality, the dual problem is found to be

Introducing a Moreau-Yosida approximation of the box constraints and a smoothing term, this problem can be solved using a superlinearly convergent semi-smooth Newton method: Given p^k, find p^k+1 satisfying

where χ_k⁺ = {x : p^k(x) > 1},χ_k^- = {x : p^k(x) < -1} denote the active sets, c > 0 is the penalty parameter for the Moreau-Yosida approximation and β > 0 is the smoothing parameter to ensure semi-smoothness. It can be shown that the dual solution p_α acts as a noise indicator. The solution of the primal problem () is then given by x_α = K^*p _α.

The parameter choice method for α is based on a balancing principle: Fix σ > 1 and find α such that

The balancing parameter α* can be calculated by a fixed point iteration using a model function, which is a rational interpolant of the value F(α) = ∥Kxα - yδ∥L1 + ∥xα∥L22 and its derivative F′(α) = ∥xα∥L22 at the iterates.

Results

Inverse source problem for the Laplace operator (i.e., K = (-Δ)^-1), 30% of data corrupted by random-valued noise:

(a) exact solution	(b) noisy data	(c) reconstruction

Reference: A semismooth Newton method for L1 data fitting with automatic choice of regularization parameters and noise calibration, submitted (preprint and Matlab code)