Abstract
Sign information is the key to overcoming the inevitable saturation error in compressive sensing systems, which causes information loss and results in bias. For sparse signal recovery from saturation, we propose to use a linear loss to improve the effectiveness from existing methods that utilize hard constraints/hinge loss for sign consistency. Due to the use of linear loss, an analytical solution in the update progress is obtained, and some nonconvex penalties are applicable, e.g., the minimax concave penalty, the $\ell_0$ norm, and the sorted $\ell_1$ norm. Theoretical analysis reveals that the estimation error can still be bounded. Generally, with linear loss and nonconvex penalties, the recovery performance is significantly improved, and the computational time is largely saved, which is verified by the numerical experiments.
Introduction
In real-world sensing applications such as digital photography and medical imaging, detectors often have a limited dynamic range. When a signal exceeds this range, it "saturates" the sensor, leading to clipped data. In Compressive Sensing (CS), this saturation introduces significant bias and error if not properly handled. Standard recovery algorithms like LASSO often fail because they assume a linear relationship across the entire measurement range. While existing "saturation-consistent" methods attempt to address this by enforcing hard constraints or using hinge loss functions, these approaches are computationally intensive and slow, limiting their use in real-time or large-scale applications.
Proposed Methodology
This paper introduces the M1bit-CS-L (Mixed one-bit Compressive Sensing with Linear loss) framework. The core innovation is the replacement of complex inequality constraints with a simple linear loss term. This term encourages the estimated signal to move in the correct direction relative to the saturation threshold (e.g., if a measurement was saturated at the maximum, the algorithm is encouraged to keep the estimate high).
By utilizing a linear loss, the authors can incorporate various nonconvex penalties—such as the Minimax Concave Penalty (MCP), the $\ell_0$ norm, and the sorted $\ell_1$ norm—to promote sparsity more effectively than the standard $\ell_1$ norm. Furthermore, the optimization problem is solved using the Alternating Direction Method of Multipliers (ADMM). The linear loss allows for closed-form analytical solutions in the ADMM sub-steps, drastically reducing computational overhead and making the algorithm roughly 10 times faster than state-of-the-art methods. The authors also provide a theoretical error bound proving that the estimation error remains bounded despite the simplification.
Experimental Results
The proposed method was evaluated using synthetic $K$-sparse signals and random Gaussian sensing matrices. Performance was measured against varying saturation ratios (0% to 50%) and signal sparsity levels.
As shown in Figure 3, the proposed algorithms significantly outperform standard LASSO and competing methods like RDCS in high-saturation environments. Specifically, the variants using MCP and sorted $\ell_1$ penalties (sL1) demonstrate superior robustness, maintaining high Signal-to-Noise Ratio (SNR) and low Angular Error (AE) even when 50% of the data is clipped.
Figure 4 highlights the effectiveness of nonconvex penalties as the number of non-zero components ($K$) increases. The proposed framework maintains lower angular error and higher SNR over a wider range of sparsity levels compared to baseline methods. The results confirm that nonconvexity helps in "pushing" small coefficients to zero more effectively than standard $\ell_1$ regularization.
Conclusion
The use of linear loss combined with nonconvex penalties provides a powerful and efficient solution for signal recovery from saturated measurements. While the current study relies on synthetic Gaussian data, the theoretical error bounds and significant speed improvements suggest broad applicability. Future work may explore the method's performance with real-world sensor noise and non-linearities beyond simple clipping.
Summary updated