Iterative Reweighted Minimization for Generalized Norm/Quasi-Norm Difference Regularized Unconstrained Nonlinear Programming

Yi Cen, Linna Zhang, Ke WangIEEE Access 2019 · OpenReview

Introduction

Sparse signal recovery is a fundamental challenge in compressed sensing, medical imaging, and data science. The goal is to reconstruct a high-dimensional signal from a limited number of linear measurements, leveraging the prior knowledge that the signal is sparse. While the $l_0$ "norm" is the ideal metric for sparsity, its minimization is NP-hard. Convex relaxations like the $l_1$ norm are computationally efficient but often require more measurements than necessary. Nonconvex alternatives, such as the $l_p$ quasi-norm ($0 < p < 1$) and the $l_1 - l_2$ difference, have been proposed to bridge this gap. This paper introduces a generalized metric: the $l_{p-q}$ difference ($0 < p \le 1, q \ge 1, p \ne q$), and provides a robust iterative framework for its optimization.

The $l_{p-q}$ Metric and Sparsity Promotion

The proposed $l_{p-q}$ metric is defined as the difference between the $l_p$ and $l_q$ norms/quasi-norms. The core insight is that this difference creates a function that is "more concave" near the origin compared to the standard $l_p$ norm. This sharper geometry is more effective at pushing small coefficients toward zero, thereby promoting higher sparsity in the recovered signal.

Level sets of various $l_{p-q}$ metrics compared to standard $l_1$ and $l_{1/2}$ norms.

As shown in the figure above, the level sets of the $l_{p-q}$ difference (e.g., $l_{1/2-1}$ or $l_{1-1.1}$) exhibit a more "star-shaped" or "spiky" contour than the standard $l_1$ diamond or the $l_{1/2}$ curve. This geometric property allows the optimization algorithm to find sparser solutions that better fit the underlying data.

The $IRL_{t,p-q}$ Algorithm

To solve the resulting nonconvex and non-Lipschitz optimization problem, the authors propose the $IRL_{t,p-q}$ algorithm. This method utilizes an iterative reweighted minimization strategy, where each step involves solving a weighted $l_t$ minimization subproblem ($t \ge 1$). By using an $\varepsilon$-approximation to handle the non-smoothness at the origin, the algorithm ensures numerical stability.

For scenarios involving ill-conditioned sensing matrices—where measurements are highly correlated—the authors introduce a variant combining the Difference of Convex functions Algorithm (DCA) with the Alternating Direction Method of Multipliers (ADMM). This hybrid approach enhances the solver's ability to escape poor local minima and find the global sparse solution.

Theoretical Contributions

The paper provides rigorous theoretical foundations for the proposed methods:

  1. Sparse Recovery Conditions: The authors establish exact and stable recovery conditions for the $l_{p-q}$ constrained problem under an extended restricted $p$-isometry property (p-RIP).
  2. Convergence Analysis: It is proven that the $IRL_{t,p-q}$ algorithm converges to a stationary point satisfying first-order optimality conditions.
  3. Superlinear Convergence: Under specific conditions, the local convergence rate is shown to be superlinear, meaning the algorithm requires significantly fewer iterations to reach high precision compared to standard first-order methods.

Experimental Evaluation

The effectiveness of the $l_{p-q}$ framework was validated across multiple domains:

  • Synthetic Sparse Recovery: In tests with Gaussian sensing matrices, $IRL_{t,p-q}$ maintained a 100% success rate at sparsity levels where $l_1$ and $l_p$ methods failed.
  • Image Reconstruction: For patch-wise reconstruction of grayscale images at a 30% sampling rate, the method achieved PSNR improvements of 0.5 to 1.0 dB over state-of-the-art nonconvex solvers.
  • Face Clustering and Low-Rank Completion: The method was applied to the Yale Face Database and ORL datasets, demonstrating superior clustering accuracy and robust performance in low-rank tensor completion tasks compared to methods like Latent Low-Rank Representation (LatLRR).

Conclusion

The $l_{p-q}$ difference provides a powerful and flexible metric for sparse recovery, generalizing several existing models. By combining this metric with an efficient iterative reweighted minimization algorithm, the authors provide a tool that is both theoretically sound and practically superior to traditional $l_1$ and $l_p$ approaches. Future work will focus on automated parameter selection and extending the framework to structured sparsity in higher-dimensional data.

Summary updated

Abstract

In this paper, we study the minimization of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l_{p-q}$ </tex-math></inline-formula> ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$0 &lt; p\le 1,~q\ge 1,~p \ne q$ </tex-math></inline-formula> ), the general difference of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l_{p}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l_{q}$ </tex-math></inline-formula> norms/quasi-norms, as a nonconvex metric for solving unconstrained nonlinear programming. We first establish an exact (stable) sparse recovery condition for the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l_{p-q}$ </tex-math></inline-formula> constrained problem under an extended restricted <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> -isometry property and then propose an iterative algorithm for the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l_{p-q}$ </tex-math></inline-formula> regularized unconstrained minimization based on the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -variant of the iterative reweighted minimization method ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t\ge 1$ </tex-math></inline-formula> ) and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula> -approximation. We theoretically prove that the proposed algorithm converges to a stationary point satisfying the first-order optimality condition. In particular, we provide a convergence rate analysis of the method and show that the local convergence is superlinear under a certain condition. Our extensive experimental results demonstrate that if the sensing matrix satisfies the restricted <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> -isometry property, the proposed iterative reweighted minimization method for the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$l_{p-q}$ </tex-math></inline-formula> unconstrained problem generally outperforms the existing methods (especially for those methods based on the difference of norms). For the ill-conditioned sensing matrix, a variant of our method via the difference of convex functions algorithm (DCA) shows better performance on the frequency of success for signal sparse recovery. Likewise, our methods are illustrated to be valid and generally outperform the existing methods for real images.
BibTeX
@inproceedings{cen2019iterative,
  author = {Yi Cen and Linna Zhang and Ke Wang and Yigang Cen},
  title = {{Iterative Reweighted Minimization for Generalized Norm/Quasi-Norm Difference Regularized Unconstrained Nonlinear Programming}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=b-1qBitb_vP},
}
Figure