Truncated Huber Penalty for Sparse Signal Recovery with Convergence Analysis

Li Yang, Serena Morigi, Michael K. Ng, You-Wei Wen

Sparse signal recovery—the art of reconstructing a signal from far fewer measurements than traditional theory suggests—is a cornerstone of modern signal processing, from MRI scans to machine learning. However, researchers have long faced a "Goldilocks" problem: the $L_0$ penalty is perfectly unbiased but computationally impossible (NP-hard), while the $L_1$ penalty is computationally friendly but introduces "estimation bias," often underestimating the very peaks we want to recover.

In a new paper titled "Truncated Huber Penalty for Sparse Signal Recovery with Convergence Analysis," Li Yang and colleagues propose a clever middle ground: the Truncated Huber (TH) penalty. This approach bridges the gap between unbiased recovery and differentiable optimization, offering a robust, fast, and mathematically sound alternative to traditional methods.

TL;DR

The authors introduce a Truncated Huber (TH) penalty that applies quadratic regularization to small signal entries while "truncating" (applying a constant penalty) to large ones. This eliminates the estimation bias found in $L_1$ methods and, when paired with their proposed Block Coordinate Descent (BCD) algorithm, achieves faster and more accurate signal recovery than state-of-the-art non-convex solvers.

What Problem Does This Paper Address?

In sparse recovery, we want to find a vector $x$ that is mostly zeros but satisfies $Ax = b$.

  1. The $L_0$ Problem: Counting non-zero entries ($L_0$ norm) is the "purest" way to enforce sparsity, but it's discrete and discontinuous, making optimization a nightmare.
  2. The $L_1$ Problem: The $L_1$ norm is a popular convex proxy. It’s easy to solve, but it penalizes large coefficients linearly. This means the larger a signal component is, the more it gets "shrunk" toward zero, leading to biased results.
  3. The Non-Convex Struggle: Existing non-convex penalties (like MCP or SCAD) try to fix this bias but often introduce non-differentiable points that make algorithms unstable or slow.

The authors sought a penalty that is differentiable at the optima, unbiased for large signals, and computationally efficient.

Methods

The core innovation is the Truncated Huber (TH) function: $$\phi_\mu(x) = \min\left(1, \frac{x^2}{\mu^2}\right)$$ - For small values ($|x| \le \mu$): It acts like a quadratic ($L_2$) penalty, smoothing out noise and negligible entries. - For large values ($|x| > \mu$): It hits a ceiling. Because the penalty is constant for large magnitudes, it doesn't "push" on them, resulting in zero estimation bias for significant signal components.

To solve this, the authors developed a Block Coordinate Descent (BCD) algorithm. They use a "surrogate function" to transform the difficult non-convex problem into a sequence of simpler sub-problems:

  1. $x$-update: Solving a weighted linear system (essentially a modified least-squares problem).
  2. $\omega$-update: A simple hard-thresholding step.

They also implement a $\mu$-continuation strategy, starting with a large threshold $\mu$ and gradually shrinking it. This stabilizes the matrix inversions and helps the algorithm avoid getting stuck in poor local minima.

Datasets

The authors validated their approach using several benchmarks:

  • Synthetic Sparse Signals: Generated using Gaussian sensing matrices and oversampled Partial Discrete Cosine Transform (DCT) matrices.
  • 1D Signals: The "MakeSignal" library from Wavelab (piecewise constant signals with noise).
  • 2D Images: A natural image of a building and sky used to test smoothing and edge preservation.

Key Insights and Ideas

  • Differentiability at the Finish Line: While the TH penalty has "kinks" at $|x| = \mu$, the authors mathematically prove that the optimal solution will never actually land on those points. This ensures the function is effectively differentiable at the optimum, allowing for smoother convergence.
  • Local Optimality: They demonstrate that for a well-chosen $\mu$, any $s$-sparse solution that could be recovered by $L_0$ is also a local optimum for the TH penalty.
  • The "Filter" Operator: The introduction of an auxiliary variable $\omega$ acts as a binary filter, adaptively distinguishing between "edges" (significant entries) and "noise" (negligible entries) during the optimization process.

Key Results

  • Speed: In noise-free recovery tests, the TH method was nearly 10 times faster than several competing non-convex methods (like MCP and $TL_1$) while maintaining high success rates.
  • Accuracy: Under noisy conditions, the TH method consistently achieved the lowest Relative Recovery Error (RRE). For example, in decaying signal tests, it was the only method to accurately reconstruct the full dynamic range of the signal (from $10^{-2}$ to $10^2$).
  • Image Smoothing: When extended to the gradient domain, the TH penalty outperformed Total Variation (TV) and Bilateral Filtering. It successfully smoothed out textures (like wrinkles in clothing) while keeping sharp boundaries (like the edge of a building against the sky) perfectly crisp.

Limitations and Future Work

While the results are impressive, the authors note a few areas for growth:

  • Parameter Tuning: The performance depends on choosing the right regularization parameter $\alpha$ and threshold $\mu$. Currently, these are often selected manually or through heuristics.
  • Adaptive Selection: Future work will focus on "adaptive $\mu$-selection" schemes to make the algorithm more "plug-and-play."
  • Deep Learning Integration: The authors suggest that the TH framework could be integrated into deep learning architectures (e.g., as a specialized loss function or layer) for even more complex image processing tasks.

Summary updated

BibTeX
@article{yang2026truncated,
  author = {Li Yang and Serena Morigi and Michael K. Ng and You-Wei Wen},
  title = {{Truncated Huber Penalty for Sparse Signal Recovery with Convergence Analysis}},
  journal = {SIAM J. Sci. Comput.},
  year = {2026},
  doi = {10.1137/25m1748184},
}
Figure