Introduction
Sparse signal recovery is a fundamental challenge in modern signal processing, essential for applications ranging from medical imaging (MRI) to machine learning. The goal is to reconstruct a signal from significantly fewer measurements than suggested by traditional sampling theory. Historically, researchers have faced a trade-off: the $L_0$ norm provides perfectly unbiased recovery but is computationally NP-hard, while the $L_1$ norm is computationally efficient but introduces "estimation bias" by underestimating large signal components.
In this work, we present the Truncated Huber (TH) penalty, a novel approach that bridges the gap between unbiased recovery and differentiable optimization. The TH penalty offers a robust, fast, and mathematically sound alternative to traditional sparse recovery methods.
Problem Statement
In sparse recovery, we seek a vector $x$ that is mostly zeros (sparse) while satisfying the linear system $Ax = b$.
- The $L_0$ Norm: Counting non-zero entries is the ideal way to enforce sparsity, but its discrete and discontinuous nature makes optimization intractable.
- The $L_1$ Norm: As a convex proxy, the $L_1$ norm is easy to solve but penalizes large coefficients linearly. This "shrinks" significant signal components toward zero, leading to biased estimations.
- Non-Convex Penalties: Existing alternatives like MCP or SCAD attempt to mitigate bias but often introduce non-differentiable points, leading to algorithmic instability or slow convergence.
The Truncated Huber Penalty
The core innovation is the Truncated Huber (TH) function, defined as: $$\phi_\mu(x) = \min\left(1, \frac{x^2}{\mu^2}\right)$$
This function is designed to handle signal entries differently based on their magnitude. For small values ($|x| \le \mu$), it acts as a quadratic ($L_2$) penalty, effectively smoothing out noise. For large values ($|x| > \mu$), the penalty reaches a constant ceiling. Because the penalty does not increase with magnitude beyond $\mu$, it exerts no "shrinkage" force on large components, resulting in zero estimation bias for significant signal features.
As shown in the figure above, the TH penalty (red and orange curves) provides a smooth approximation to the $L_0$ penalty (green) while avoiding the linear growth of the $L_1$ penalty (blue).
Optimization: Block Coordinate Descent
To solve the optimization problem associated with the TH penalty, we developed a Block Coordinate Descent (BCD) algorithm. The approach utilizes a surrogate function to transform the non-convex problem into a sequence of simpler sub-problems:
- $x$-update: Solving a weighted linear system, which is essentially a modified least-squares problem.
- $\omega$-update: A simple hard-thresholding step where $\omega$ acts as an auxiliary binary filter, distinguishing between significant signal entries and noise.
A key component of the algorithm is the $\mu$-continuation strategy. By starting with a large threshold $\mu$ and gradually decreasing it, we stabilize matrix inversions and help the algorithm avoid poor local minima.
Convergence and Local Optimality
Theoretical analysis reveals two critical properties:
- Differentiability at Optima: Although the TH penalty has non-differentiable points at $|x| = \mu$, the authors prove that optimal solutions never reside on these points. This ensures the function is effectively differentiable at the optimum, facilitating smooth convergence.
- Local Optimality: For a properly chosen $\mu$, any $s$-sparse solution recoverable by the $L_0$ norm is also a local optimum for the TH penalty.
Experimental Evaluation
The TH method was validated using synthetic sparse signals (Gaussian and DCT matrices), 1D piecewise constant signals, and 2D natural images.
Key Results
- Computational Efficiency: In noise-free tests, the TH method was approximately 10 times faster than competing non-convex solvers like MCP and $TL_1$ while maintaining high success rates.
- Recovery Accuracy: Under noisy conditions, TH consistently achieved the lowest Relative Recovery Error (RRE). In tests with decaying signals, it was uniquely capable of reconstructing the full dynamic range (from $10^{-2}$ to $10^2$).
- Image Processing: When applied to image smoothing in the gradient domain, the TH penalty outperformed Total Variation (TV) and Bilateral Filtering, successfully removing textures while preserving sharp boundaries.
Conclusion
The Truncated Huber penalty provides a powerful framework for sparse signal recovery, combining the unbiased nature of $L_0$ with the computational advantages of differentiable optimization. Future work will explore adaptive $\mu$-selection schemes to improve the "plug-and-play" capability of the algorithm and investigate its integration into deep learning architectures as a specialized loss function.
Summary updated