A Unified Approach to Uniform Signal Recovery From Nonlinear Observations

Martin Genzel, Alexander Stollenwerk

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.

Geometric representation of the intersection between the signal set $K$ and a sphere of radius $t$ centered at $Tx$, used to analyze local complexity.

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

Abstract

Recent advances in quantized compressed sensing and high-dimensional estimation have shown that signal recovery is even feasible under strong non-linear distortions in the observation process. An important characteristic of associated guarantees is uniformity, i.e., recovery succeeds for an entire class of structured signals with a fixed measurement ensemble. However, despite significant results in various special cases, a general understanding of uniform recovery from non-linear observations is still missing. This paper develops a unified approach to this problem under the assumption of i.i.d. sub-Gaussian measurement vectors. Our main result shows that a simple least-squares estimator with any convex constraint can serve as a universal recovery strategy, which is outlier robust and does not require explicit knowledge of the underlying non-linearity. Based on empirical process theory, a key technical novelty is an approximative increment condition that can be implemented for all common types of non-linear models. This flexibility allows us to apply our approach to a variety of problems in non-linear compressed sensing and high-dimensional statistics, leading to several new and improved guarantees. Each of these applications is accompanied by a conceptually simple and systematic proof, which does not rely on any deeper properties of the observation model. On the other hand, known local stability properties can be incorporated into our framework in a plug-and-play manner, thereby implying near-optimal error bounds.
BibTeX
@article{genzel2023unified,
  author = {Martin Genzel and Alexander Stollenwerk},
  title = {{A Unified Approach to Uniform Signal Recovery From Nonlinear Observations}},
  journal = {Found. Comput. Math.},
  year = {2023},
  doi = {10.1007/s10208-022-09562-y},
}
Figure