A Unified Feasible SQP Framework for sparse and non-negative sparse recovery

Abstract Sparse signal recovery is a central problem in many areas, including medical imaging, remote sensing, machine learning, and data science. In many practical settings, the underlying signal is inherently non-negative, due to the physical nature of the measured quantities (e.g., pixel intensities, chemical concentrations, or power spectra). Although there is extensive work on general sparse recovery and a growing literature on non-negative sparse recovery, there has been no unified theoretical and algorithmic framework that can naturally handle both cases within a single formulation. We propose a unified feasible sequential quadratic programming (SQP) framework that treats both general and non-negative sparse recovery as special cases of one constrained optimization model, distinguished only by the geometry of the trust region used to enforce feasibility. The framework is based on the Smoothed- $$\ell ^0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msup> </mml:math> (SL0) approximation, which provides a smooth, non-convex surrogate for the combinatorial $$\ell ^0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>ℓ</mml:mi> <mml:mn>0</mml:mn> </mml:msup> </mml:math> norm. By exploiting the exact diagonal structure of the Hessian of the SL0 objective, we obtain accurate second-order search directions and achieve a superlinear convergence rate, improving significantly over the first-order methods that dominate the literature. For the non-negative case, we incorporate interior-point ideas directly into the SQP subproblem. Instead of using post hoc projections or hard thresholding, which can disrupt convergence and cause numerical instability near the boundary, we impose an ellipsoidal trust region that keeps all iterates strictly inside the non-negative orthant. This leads to a stable and theoretically sound algorithm. The non-negative method is initialized with a simple, robust all-ones vector, avoiding the potential instabilities associated with pseudo-inverse-based initializations. We establish global convergence of the unified framework under the standard Mangasarian–Fromovitz Constraint Qualification (MFCQ). Numerical experiments on both synthetic data and real-world tasks such as face recognition show that the proposed approach outperforms a wide range of state-of-the-art algorithms in terms of recovery accuracy (SNR, SRR), phase transition behavior, and robustness to noise.