LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
Consider estimating an unknown, but structured (e.g. sparse, low-rank, etc.), signal x 0 ∈ R n from a vector y ∈ R m of measurements of the form 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) = 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, i.e.,x := arg min x y − Ax 0 2 + λf (x) for some regularization parameter λ > 0 and some (typically non-smooth) convex regularizer f (·) that promotes the structure of x 0 , e.g. 1 -norm, nuclear-norm, etc. 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 µ, which only depends on g(·). In this work, we considerably strengthen these results by obtaining explicit expressions for x−µx 0 2 , for the regularized Generalized-LASSO, that are asymptotically precise when m and n 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 y i = µa i T x 0 + σz i , 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 Generalized LASSO is the celebrated Lloyd-Max quantizer.
Summary: This paper considers the Generalized Lasso with non-linear measurements and Gaussian design. A known heuristic often used is that non-linear observations may be treated as noisy linear observations. Capitalizing on the work of Plan and Vershynin [17], the authors here extend the results of [17], and by moving to an asymptotic regime, they provide novel precise explicit expressions of the error estimation. The accuracy of their predictions is confirmed with many special cases (including the Lasso, the group Lasso and the nuclear norm). The application to the design of optimal quantizers in the context of q-Bit CS and its relation to the Lloyd-Max quantizer is very insightful.             Quality: This is a nice piece of work.            Clarity: The paper is quite well-written, though the treatment is somewhat unbalanced. The lack of space however prevents including all the necessary details.                  Originality: The paper builds upon the work of Plan and Vershynin [17] and expands in several aspects that are novel. For instance, the explicit expressions of the performance estimation error are new.            Comments:     1) Page 4, line 193: the regularized and penalized versions are equivalent with appropriate correspondence.     2) Caption of Figure 1: 'n=768' shouldbe '$n$=768'.     3) Page 5, line 247: a typo at 'When ...'.     4) Page 5, line 294: what the authors call the proximal function is (very well) known in convex analysis as the Moreau envelope of index \tau. The notation used there is awkward as prox is generally used for the proximal point/operator but not for the Moreau envelope. I suggest changing it.     5) Page 5, Assumption 1: I think it would instructive to give this assumption a more formal interpretation using results from variational analysis.     6) The authors should avoid calling the generalized Lasso an algorithm in the text. It is certainly a (convex) program (or decoder to borrow the terminology widely used in CS), but not an algorithm.     7) Experiments: the authors show the results when applying the generalized Lasso to the non-linear measurements, and how the theorems predict the estimation error.