Fast and exact unidimensional L2-L1 optimization as an accelerator for iterative reconstruction algorithms

This paper studies the use of fast and exact unidimensional L2-L1 minimization as a line search for accelerating iterative reconstruction algorithms. In L2-L1 minimization reconstruction problems, the squared Euclidean, or L2 norm, measures signal-data discrepancy and the L1 norm stands for a sparsity preserving regularization term. Functionals as these arise in important applications such as compressed sensing and deconvolution. Optimal unidimensional L2-L1 minimization has only recently been studied by Li and Osher for denoising problems and by Wen et al. for line search. A fast L2-L1 optimization procedure can be adapted for line search and used in iterative algorithms, improving convergence speed with little increase in computational cost. This paper proposes a new method for exact L2-L1 line search and compares it with the Li and Osher's, Wen et al.'s, as well as with a standard line search algorithm, the method of false position. The use of the proposed line search improves convergence speed of different iterative algorithms for L2-L1 reconstruction such as iterative shrinkage, iteratively reweighted least squares, and nonlinear conjugate gradient. This assertion is validated experimentally in applications to signal reconstruction in compressed sensing and sparse signal deblurring.