A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing

In generative compressed sensing (GCS), we want to recover a signal x^* ∈ ℝn from m measurements (mll n) using a generative prior x^*∈ G(mathbbB2k(r)), where G is typically an L-Lipschitz continuous generative model and mathbbB2k(r) represents the radius-r ℓ2-ball in ℝk. Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed x^* rather than for all x^* simultaneously. In this paper, we build a unified framework to derive uniform recovery guarantees for nonlinear GCS where the observation model is nonlinear and possibly discontinuous or unknown. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. Specifically, using a single realization of the sensing ensemble and generalized Lasso, em all x^*∈ G(mathbbB2k(r)) can be recovered up to an ℓ2-error at most ε using roughly tildeO(k/ε2) samples, with omitted logarithmic factors typically being dominated by log L. Notably, this almost coincides with existing non-uniform guarantees up to logarithmic factors, hence the uniformity costs very little. As part of our technical contributions, we introduce the Lipschitz approximation to handle discontinuous observation models. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy. Experimental results are presented to corroborate our theory.