Nonconvex Regularization-Based Sparse Recovery and Demixing With Application to Color Image Inpainting

Abstract

This paper addresses the recovery and demixing problem of signals that are sparse in some general dictionary. Involved applications include source separation, image inpainting, super-resolution, and restoration of signals corrupted by clipping, saturation, impulsive noise, or narrowband interference. We employ the ℓq-norm (0 ≤ q <; 1) for sparsity inducing and propose a constrained ℓq-minimization formulation for the recovery and demixing problem. This nonconvex formulation is approximately solved by two efficient first-order algorithms based on proximal coordinate descent and alternative direction method of multipliers (ADMM), respectively. The new algorithms are convergent in the nonconvex case under some mild conditions and scale well for high-dimensional problems. A convergence condition of the new ADMM algorithm has been derived. Furthermore, the extension of the two algorithms for multichannels joint recovery has been presented, which can further exploit the joint sparsity pattern among multichannel signals. Various numerical experiments showed that the new algorithms can achieve considerable performance gain over the ℓ1-regularized algorithms.

Keywords

• Alternative direction method of multipliers
• proximal coordinate descent
• ℓq-norm minimization
• sparse recovery
• signal separation
• inpainting