Computational approaches to non-convex, sparsity-inducing multi-penalty regularization

Inverse Problems, vol. 37, pp. 055008

Abstract

Abstract In this work we consider numerical efficiency and convergence rates for solvers of non-convex multi-penalty formulations when reconstructing sparse signals from noisy linear measurements. We extend an existing approach, based on reduction to an augmented single-penalty formulation, to the non-convex setting and discuss its computational intractability in large-scale applications. To circumvent this limitation, we propose an alternative single-penalty reduction based on infimal convolution that shares the benefits of the augmented approach but is computationally less dependent on the problem size. We provide linear convergence rates for both approaches, and their dependence on design parameters. Numerical experiments substantiate our theoretical findings.

Authors 3

1. Željko Kereta corresponding

   University College London · Simula Research Laboratory · Simula Metropolitan Center for Digital Engineering

   Affiliation as printed

   Simula Research Laboratory, Simula Metropolitan Center for Digital Engineering, Norway

   University College London, United Kingdom

   Simula Research Laboratory;

2. Johannes Maly Aachen

   RWTH Aachen University · Catholic University of Eichstätt-Ingolstadt

   Affiliation as printed

   RWTH Aachen University, Germany

   Catholic University of Eichstätt-Ingolstadt

3. Valeriya Naumova

   Simula Research Laboratory · Simula Metropolitan Center for Digital Engineering

   Affiliation as printed

   Simula Research Laboratory, Simula Metropolitan Center for Digital Engineering, Norway

   Simula Research Laboratory;