Poster
LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
CHRISTOS THRAMPOULIDIS · Ehsan Abbasi · Babak Hassibi
210 C #82
[
Abstract
]
Abstract:
Consider estimating an unknown, but structured (e.g. sparse, low-rank, etc.), signal x0∈Rnx0∈Rn from a vector y∈Rmy∈Rm of measurements of the form yi=gi(aTix0)yi=gi(aTix0), where the aiai's are the rows of a known measurement matrix AA, and, gg 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)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 estimate x0x0 via solving the Generalized-LASSO, i.e., ˆx=argminx‖y−Ax0‖2+λf(x)^x=argminx∥y−Ax0∥2+λf(x) for some regularization parameter λ>0λ>0 and some (typically non-smooth) convex regularizer ff that promotes the structure of x0x0, e.g. ℓ1ℓ1-norm, nuclear-norm. While this approach seems to naively ignore the nonlinear function gg, both Brillinger and Plan and Vershynin have shown that, when the entries of AA are iid standard normal, this is a good estimator of x0x0 up to a constant of proportionality μμ, which only depends on gg. In this work, we considerably strengthen these results by obtaining explicit expressions for ‖ˆx−μx0‖2∥^x−μx0∥2, for the regularized Generalized-LASSO, that are asymptotically precise when mm and nn grow large. A main result is that the estimation performance of the Generalized LASSO with non-linear measurements is asymptotically the same as one whose measurements are linear yi=μaTix0+σziyi=μaTix0+σzi, with μ=E[γg(γ)]μ=E[γg(γ)] and σ2=E[(g(γ)−μγ)2]σ2=E[(g(γ)−μγ)2], and, γγ standard normal. 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.
Live content is unavailable. Log in and register to view live content