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

Fei Wen, Lasith Adhikari, Ling Pei, Roummel F. Marcia, Peilin Liu, Robert C. Qiu

Abstract

This work 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 $\ell_q$-norm ($0 \le q < 1$) for sparsity inducing and propose a constrained $\ell_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, extension of the two algorithms for multi-channels joint recovery has been presented, which can further exploit the joint sparsity pattern among multi-channel signals. Various numerical experiments showed that the new algorithms can achieve considerable performance gain over the $\ell_1$-regularized algorithms.

Introduction

Sparse recovery and demixing involve separating a signal into constituent parts that are sparse in a specific mathematical domain. While $\ell_1$-regularization (the Lasso) is the standard approach due to its convexity, it often suffers from a "bias problem," underestimating large coefficients and leading to suboptimal reconstructions. This paper explores the use of nonconvex $\ell_q$-norms ($0 \le q < 1$), which more effectively promote true sparsity. Despite the optimization challenges posed by nonconvex landscapes, the authors demonstrate that these norms significantly improve performance in applications like color image inpainting and robust signal recovery.

Methodology

The core of the research is a constrained $\ell_q$-minimization formulation for the signal mixture $y = A_1x_1 + A_2x_2$. To solve this, two first-order algorithms were developed:

  1. Proximal Block Coordinate Descent (BCD): This method updates variables alternately using a quadratic majorization technique to handle nonconvexity.
  2. 4-Block ADMM: A novel variation of the Alternative Direction Method of Multipliers designed to ensure convergence in nonconvex settings. The authors provide a mathematical proof (Theorem 2) establishing the conditions for stable convergence to a critical point.
  3. Multichannel Joint Recovery: For color (RGB) images, the algorithms exploit inter-channel correlations using a joint-sparsity $\ell_{2,q}$ norm, significantly boosting reconstruction quality compared to independent channel processing.

Experimental Results

The proposed methods were evaluated using synthetic data and standard color image benchmarks. Synthetic tests revealed that $\ell_q$ methods ($q \in [0.2, 0.7]$) consistently outperform the $\ell_1$ standard ($q=1$) as signal sparsity increases.

Frequency of success vs. sparsity K for various algorithms and q values. The lq variants (q < 1) maintain high success rates at much higher sparsity levels than the l1 baseline (q=1).

In color image inpainting with 30% impulsive noise, the BCD method achieved a PSNR of 34.62 dB, a substantial improvement over the 25.80 dB achieved by the $\ell_1$-based YALL1 solver. Furthermore, the algorithms proved efficient, processing $512 \times 512$ images in under 50 seconds.

Convergence and Robustness

A critical contribution of this work is the theoretical and empirical demonstration of algorithm convergence. Figure 3 illustrates the stable descent of the objective function across iterations for various $q$ values, confirming that the nonconvexity does not prevent reaching a stable solution.

Convergence behavior showing the change in x1 updates over iterations. The algorithms reach a stable state efficiently across different q parameters.

The methods also showed superior robustness against heavy-tailed noise models, such as symmetric $\alpha$-stable ($S\alpha S$) noise, with relative errors approximately 40% lower than those of $\ell_1$ methods.

Conclusion

This research demonstrates that nonconvex $\ell_q$ regularization provides a powerful framework for sparse recovery and demixing. By proving the convergence of efficient first-order algorithms like the 4-block ADMM, the authors bridge the gap between theoretical rigor and practical performance. Future work may involve automating hyperparameter selection and integrating these nonconvex priors with learned dictionaries to further enhance signal restoration capabilities.

Summary updated

Abstract

This work 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 $\ell_q$-norm ($0 \le q < 1$) for sparsity inducing and propose a constrained $\ell_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, extension of the two algorithms for multi-channels joint recovery has been presented, which can further exploit the joint sparsity pattern among multi-channel signals. Various numerical experiments showed that the new algorithms can achieve considerable performance gain over the $\ell_1$-regularized algorithms.
BibTeX
@article{wen2017nonconvex,
  author = {Fei Wen and Lasith Adhikari and Ling Pei and Roummel F. Marcia and Peilin Liu and Robert C. Qiu},
  title = {{Nonconvex Regularization Based Sparse Recovery and Demixing with Application to Color Image Inpainting}},
  journal = {IEEE Access},
  year = {2017},
  doi = {10.1109/access.2017.2705646},
}
Figure