The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements by Chrtistos Thrampoulidis, Ehsan Abbasi, Babak Hassibi

Consider estimating an unknown, but structured, signalx0∈Rn fromm measurementyi=gi(aTix0) , where theai 's are the rows of a known measurement matrixA , 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.,gi(x)=sign(x+zi) , corresponds to noisy 1-bit quantized measurements. Motivated by the classical work of Brillinger, and more recent work of Plan and Vershynin, we estimatex0 via solving the Generalized-LASSO for some regularization parameterλ>0 and some (typically non-smooth) convex structure-inducing regularizer function. While this approach seems to naively ignore the nonlinear functiong , both Brillinger (in the non-constrained case) and Plan and Vershynin have shown that, when the entries ofA are iid standard normal, this is a good estimator ofx0 up to a constant of proportionalityμ , which only depends ong . 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} whenm andn 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 linearyi=μaTix0+σzi , withμ=Eγg(γ) andσ2=E(g(γ)−μγ)2 , and,γ 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.

**Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !**

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

## No comments:

Post a Comment