Unconstrained L1 Optimization With Applications To Signal And Image Processing

In recent years, the applied mathematical community has witnessed a revolution that is changing the paradigm of classical signal and image processing. Novel and e efficient numerical algorithms have emerged for solving new challenges in large scale signal retrieval, where both constrained and unconstrained L1 minimization methods play a fundamental role. In this work, we present a new methodology for solving unconstrained L1 minimization problems in the context of image and signal processing. Our approach consists in solving a sequence of relaxed unconstrained minimization problems depending on a positive regularization parameter that converges to zero. The optimality conditions of each subproblem are characterized through a fixed point equation, where a preconditioned conjugate gradient algorithm is applied to solve a sequence of resulting linear systems. The preconditioner used in the conjugate gradient algorithm is designed in such a way that it exploits the structure of the induced matrix at each subproblem. Moreover, we show that the distribution of the eigenvalues in the preconditioned system is bounded regardless of the value of the regularization parameter. We prove global convergence for the iterative scheme derived from our method and conduct several numerical experiments showing that the proposed algorithm performs comparable with some state of the art solvers. In particular, we present numerical evidence that our algorithm is very competitive when recovering high dynamic range signals. Finally, we solve a set of real world applications including image processing problems, data and signal processing in micrometeorology, texture segmentation in seismic data and total variation