The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements

Abstract

Consider estimating an unknown, but structured, signal $x_0\in R^n$ from $m$ measurement $y_i=g_i(a_i^T{x}_0)$, where the $a_i$'s are the rows of a known measurement matrix $A$, and, $g$ is a (potentially unknown) nonlinear and random link-function. Such measurement functions could arise in applications where the measurement device has nonlinearities and uncertainties. It could also arise by design, e.g., $g_i(x)=\text{sign}(x+z_i)$, corresponds to noisy 1-bit quantized measurements. Motivated by the classical work of Brillinger, and more recent work of Plan and Vershynin, we estimate $x_0$ via solving the Generalized-LASSO for some regularization parameter $\lambda >0$ and some (typically non-smooth) convex structure-inducing regularizer function. While this approach seems to naively ignore the nonlinear function $g$, both Brillinger (in the non-constrained case) and Plan and Vershynin have shown that, when the entries of $A$ are iid standard normal, this is a good estimator of $x_0$ up to a constant of proportionality $\mu$, which only depends on $g$. In this work, we considerably strengthen these results by obtaining explicit expressions for the squared error, for the \emph{regularized} LASSO, that are asymptotically \emph{precise} when $m$ and $n$ grow large. A main result is that the estimation performance of the Generalized LASSO with non-linear measurements is \emph{asymptotically the same} as one whose measurements are linear $y_i=\mu a_i^T{x}_0+\sigma z_i$, with $\mu =E\gamma g(\gamma )$ and ${\sigma }^2=E(g(\gamma )-\mu \gamma {)}^2$, and, $\gamma$ standard normal. To the best of our knowledge, the derived expressions on the estimation performance are the first-known precise results in this context. One interesting consequence of our result is that the optimal quantizer of the measurements that minimizes the estimation error of the LASSO is the celebrated Lloyd-Max quantizer.

References in corpus (5)

• Message Passing Algorithms for Compressed Sensing
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• A framework to characterize performance of LASSO algorithms
• Structured sparsity-inducing norms through submodular functions
• Optimal linear estimation under unknown nonlinear transform

Cited by in corpus (27)

• High-dimensional estimation with geometric constraints
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• A Model of Double Descent for High-dimensional Binary Linear Classification
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• Structured signal recovery from non-linear and heavy-tailed measurements
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• The Generalized Lasso with Nonlinear Observations and Generative Priors
• Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data
• Inference In High-dimensional Single-Index Models Under Symmetric Designs
• Quantized Corrupted Sensing with Random Dithering
• A Unified Approach to Uniform Signal Recovery From Non-Linear Observations
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Precise Error Analysis of the LASSO under Correlated Designs
• The Mismatch Principle: The Generalized Lasso Under Large Model Uncertainties
• Misspecified Nonconvex Statistical Optimization for Phase Retrieval
• Regularized Nonlinear Regression for Simultaneously Selecting and Estimating Key Model Parameters
• Out-of-sample error estimate for robust M-estimators with convex penalty
• Optimum GSSK Transmission in Massive MIMO Systems Using the Box-LASSO Decoder
• Optimizing quantization for Lasso recovery
• Scalable Approximations for Generalized Linear Problems
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective
• II. High Dimensional Estimation under Weak Moment Assumptions: Structured Recovery and Matrix Estimation