Lifting high-dimensional nonlinear models with Gaussian regressors

Abstract

We study the problem of recovering a structured signal ${\mathbf{x}}_0$ from high-dimensional data ${\mathbf{y}}_i=f({\mathbf{a}}_i^T{\mathbf{x}}_0)$ for some nonlinear (and potentially unknown) link function $f$, when the regressors ${\mathbf{a}}_i$ are iid Gaussian. Brillinger (1982) showed that ordinary least-squares estimates ${\mathbf{x}}_0$ up to a constant of proportionality ${\mu }_{\ell }$, which depends on $f$. Recently, Plan & Vershynin (2015) extended this result to the high-dimensional setting deriving sharp error bounds for the generalized Lasso. Unfortunately, both least-squares and the Lasso fail to recover ${\mathbf{x}}_0$ when ${\mu }_{\ell }=0$. For example, this includes all even link functions. We resolve this issue by proposing and analyzing an alternative convex recovery method. In a nutshell, our method treats such link functions as if they were linear in a lifted space of higher-dimension. Interestingly, our error analysis captures the effect of both the nonlinearity and the problem's geometry in a few simple summary parameters.

Improved the algorithm and expanded on its motivation; added simulation results

References in corpus (1)

• Optimal linear estimation under unknown nonlinear transform

Cited by in corpus (5)

• Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data
• A Unified Approach to Uniform Signal Recovery From Non-Linear Observations
• The Mismatch Principle: The Generalized Lasso Under Large Model Uncertainties
• Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer
• One-Bit Compressed Sensing via One-Shot Hard Thresholding