Introduction
In the field of signal processing, classical compressed sensing focuses on recovering sparse signals from a limited number of linear measurements. However, real-world acquisition systems often introduce nonlinearities, such as 1-bit quantization, multi-bit quantization, or modulo operations (common in "unlimited sampling" to prevent sensor saturation).
Historically, recovery guarantees for these nonlinear models have faced two primary challenges. First is the lack of uniformity: many theories only guarantee recovery for a fixed signal rather than for an entire class of signals (e.g., all sparse signals) using a single measurement ensemble. Second is the lack of unity: there was no single theoretical framework capable of handling smooth nonlinearities, jump discontinuities, and adversarial noise simultaneously. This paper introduces a unified mathematical framework to address these gaps.
Methodology: The Generalized Lasso
The authors demonstrate that the Generalized Lasso—a standard least-squares minimization subject to a convex constraint—serves as a universal recovery strategy. Remarkably, this estimator does not require explicit knowledge of the specific nonlinear function $F$ that generated the data. It effectively treats nonlinearities as structured noise, allowing for the recovery of signal direction and, when dithering is employed, magnitude.
The core technical innovation is the approximative increment condition. Traditional proofs often require the nonlinearity to be Lipschitz continuous (smooth). This work bypasses this constraint by showing that even discontinuous functions, such as the sign function in 1-bit sensing, can be approximated by smoother counterparts. This allows for the derivation of rigorous error bounds using empirical process theory.
Geometric Complexity and the Increment Condition
To quantify the number of measurements $m$ required for a specific accuracy $t$, the framework utilizes the Gaussian mean width, a measure of the geometric complexity of the signal set.
A key insight is the geometric decoupling of the problem. As illustrated in the figure above, the complexity can be split into the "local" complexity of the constraint set $K$ (represented by the intersection $K_{x,t}$) and the "global" size of the signal class. This decomposition simplifies the application of the theory to diverse signal structures and observation models.
Applications and Results
The framework is evaluated against several mathematical observation models using i.i.d. sub-Gaussian measurement vectors:
- 1-Bit Observations: $y = \text{sign}(\langle a, x \rangle)$. The paper improves upon previous uniform recovery rates, approaching the optimal $O(m^{-1/2})$ error decay.
- Modulo Measurements: $y = \langle a, x \rangle \pmod \lambda$. The authors provide the first uniform recovery guarantees for "unlimited sampling" models using the Lasso, even when the sensor "wraps around" multiple times.
- Dithered Quantization: Adding random noise before quantization to preserve signal magnitude.
- Outlier Robustness: The framework proves naturally robust to "gross" outliers, showing that performance degrades gracefully even with corrupted measurements.
Conclusion and Future Work
This unified approach provides a powerful "recipe" for calculating sampling rates across a wide variety of nonlinear models. However, some limitations remain. The current theory relies on i.i.d. sub-Gaussian measurement vectors, which does not yet account for structured matrices like those used in MRI. Additionally, while the framework handles discontinuities, the "out-of-the-box" error decay rate for such cases is $O(m^{-1/4})$, requiring more complex embeddings to reach the information-theoretic limit of $O(m^{-1/2})$. Future work may also explore extending these results to non-convex signal sets, such as those defined by deep generative priors.
Summary updated