A Unified Approach to Uniform Signal Recovery From Non-Linear Observations

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.

to be published in Foundations of Computational Mathematics (accepted version)

References in corpus (7)

• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
• Tight convex relaxations for sparse matrix factorization
• Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data
• The Generalized Lasso with Nonlinear Observations and Generative Priors
• Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applications