Robust Uniform Recovery of Structured Signals from Nonlinear Observations
It addresses the challenge of robust signal recovery in nonlinear settings like Gaussian single-index models, offering a unified theoretical framework that improves upon prior work.
This paper tackles the problem of uniform recovery of structured signals from nonlinear observations, showing that the restricted approximate invertibility condition (RAIC) enables projected gradient descent (PGD) to achieve uniform recovery with error rates matching existing nonuniform ones up to log factors, and in some cases without log factor loss.
While it is well known that the restricted isometry property (RIP) guarantees uniform sparse recovery from noisy linear measurements, uniform recovery of structured signals from nonlinear observations remains much less understood. This paper shows that the restricted approximate invertibility condition (RAIC) provides a unified approach to this end. Particularly, uniform recovery is achieved by projected gradient descent (PGD) with gradients obeying RAIC for all signals. As an application, under a large class of piecewise Lipschitz link functions (possibly discontinuous), we develop a uniform recovery theory for Gaussian single-index model by establishing the uniform RAIC for the gradient of the (scaled) $\ell_2$ loss via a covering argument. The theory generalizes the nonuniform recovery guarantees due to Plan and Vershynin (2016); Oymak and Soltanolkotabi (2017) and exhibits additional error terms that can be interpreted as the cost of uniform recovery. Intriguingly, in the three canonical settings of (a) sparse recovery via PGD with $\ell_0$ projection (i.e., iterative hard thresholding (IHT)), (b) sparse recovery via PGD with $\ell_1$ projection, and (c) recovering approximately sparse signals via PGD with $\ell_1$ projection, the additional error terms are negligible and in turn our uniform recovery error rates are at the same order of existing nonuniform ones, up to log factors. Our results hence improve on Genzel and Stollenwerk (2023). Under the specific nonlinearity of 1-bit quantization, we use a VC dimension argument to show that the uniform recovery error of IHT is at the same order of the nonuniform recovery error, with no loss of log factor. In addition, we show that the robustness of PGD to noise and corruption can be incorporated elegantly by bounding a single additional random process that captures the gradient mismatch.