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

TL;DR

This paper introduces novel nonconvex regularization techniques for sparse signal recovery and demixing, outperforming traditional convex methods. They propose two efficient algorithms (BCD and ADMM) that are guaranteed to converge and scale well for high-dimensional problems, with extensions for multi-channel image processing tasks like inpainting.

What Problem Does This Paper Address?

Many real-world problems, such as separating signals, restoring images (inpainting, super-resolution), and canceling interference, can be modeled as recovering sparse signals from linear measurements. Traditional methods often use L1-norm regularization to promote sparsity. However, L1-norm can lead to biased estimates for large coefficients and may not be optimal for all types of sparsity. This paper addresses the limitations of L1-norm by exploring Lq-norm regularization (where 0 < q < 1), which is known to be more effective for promoting sparsity and requires fewer measurements for reliable reconstruction. The challenge lies in the fact that Lq-norm regularization leads to a nonconvex optimization problem, making it difficult to solve efficiently and guarantee convergence.

Methods

The core contribution of this paper is the development of two novel first-order algorithms to solve the nonconvex Lq-norm minimization problem:

  • Proximal Block Coordinate Descent (BCD): This algorithm iteratively updates the sparse components by minimizing the objective function along coordinate directions. It uses a quadratic majorization technique to approximate the nonconvex subproblems, allowing for efficient updates that resemble proximity operators.
  • Proximal Alternating Direction Method of Multipliers (ADMM): This algorithm extends the powerful ADMM framework to handle the nonconvex Lq-norm problem. It introduces auxiliary variables and an augmented Lagrangian function, which is then iteratively minimized. The paper provides a convergence analysis for this ADMM algorithm, including a sufficient condition for convergence.

Both algorithms are designed to be convergent under mild conditions and scale well for high-dimensional data. The authors also extend these algorithms to a multitask setting to exploit the correlation among multiple channels in color images, further improving performance.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data for experiments and evaluates its methods on standard image datasets for the inpainting task.

Key Insights and Ideas

  • Nonconvex Lq-norm is superior to L1-norm for sparsity: The paper provides strong evidence that using Lq-norm with q < 1 leads to better recovery performance and requires fewer measurements compared to L1-norm, especially in challenging scenarios like impulsive noise.
  • Guaranteed convergence for nonconvex problems: The proposed BCD and ADMM algorithms offer a significant advancement by providing theoretical guarantees of convergence for nonconvex Lq-norm minimization, which was a major hurdle.
  • Multitask learning for color images: Exploiting the joint sparsity across color channels (e.g., RGB) leads to substantial performance gains in image recovery tasks like inpainting, demonstrating the benefit of considering inter-channel correlations.
  • Parameter selection matters: The performance of the Lq-norm methods is sensitive to the choice of q1 and q2. The paper provides insights into selecting these parameters based on the nature of the sparse signals (e.g., strictly sparse vs. compressible).

Key Results

  • Improved Recovery Accuracy: The proposed BCD and ADMM algorithms consistently outperform L1-based methods (like YALL1 and JP) in terms of recovery accuracy (measured by RelErr and PSNR) across various experiments, including synthetic sparse signal separation and color image inpainting. For instance, in color image inpainting, the proposed methods achieved PSNR improvements of 4-5 dB over YALL1.
  • Robustness to Noise: The algorithms demonstrate strong performance in the presence of impulsive noise, a common challenge in real-world applications.
  • Scalability: The algorithms are designed to handle high-dimensional problems efficiently, with computational complexity dominated by matrix-vector multiplications.
  • Multitask Performance: The multitask versions of BCD and ADMM achieved even better results by jointly recovering image channels, outperforming single-task recovery.

Limitations and Future Work

  • Parameter Tuning: While the paper shows that parameter selection is crucial, finding the optimal values for μ, q1, and q2 can still be challenging and often requires empirical tuning or cross-validation.
  • Comparison with State-of-the-Art: While the paper compares against several relevant methods, it acknowledges that specialized methods like Field of Experts (FoE) can achieve superior performance in inpainting, but these often require prior knowledge of the corruption mask, which the proposed methods do not need.
  • Future Work: The paper suggests extending the algorithms to more general multitask settings and exploring their application to other signal processing problems. Further investigation into more automated and robust parameter selection strategies would also be beneficial.

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