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.
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:
- 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).
- Convergence Analysis: It is proven that the $IRL_{t,p-q}$ algorithm converges to a stationary point satisfying first-order optimality conditions.
- 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