Truncated Huber Penalty for Sparse Signal Recovery with Convergence Analysis

Abstract. Sparse signal recovery from underdetermined systems presents significant challenges when using conventional [Formula: see text] and [Formula: see text] penalties, primarily due to computational complexity and estimation bias. This paper introduces a truncated Huber penalty, a nonconvex metric that effectively bridges the gap between unbiased sparse recovery and differentiable optimization. The proposed penalty applies quadratic regularization to small entries while truncating large magnitudes, avoiding nondifferentiable points at optimal solutions. Theoretical analysis demonstrates that, for an appropriately chosen threshold, any [Formula: see text]-sparse solution recoverable via conventional penalties remains a local optimum under the truncated Huber function. This property allows the exact and robust recovery theories developed for other penalty regularization functions to be directly extended to the truncated Huber function. To solve the optimization problem, we develop a block coordinate descent (BCD) algorithm with finite-step convergence guarantees under spark conditions. Numerical experiments validate the effectiveness and robustness of the proposed method in both synthetic and real scenarios. Furthermore, we demonstrate the flexibility of the truncated Huber framework through two extensions: one to an adaptively weighted variant inspired by sorted penalties, and the other to the gradient domain for applications such as signal denoising and image smoothing.