Asymptotically Exact Error Analysis for the Generalized ℓ^2_2LASSO
Abstract
Given an unknown signal x_0∈R^n and linear noisy measurements y=Ax_0 + σv ∈ ℝ^m, the generalized ℓ^2_2LASSO solves x^:=arg min_x 1/2∥y−Ax∥^2_2 + σλf(x). Here, f is a convex regularization function (e.g. ℓ_1norm, nuclearnorm) aiming to promote the structure of x_0 (e.g. sparse, lowrank), and, λ ≥ 0 is the regularizer parameter. A related optimization problem, though not as popular or wellknown, is often referred to as the generalized ℓ_2LASSO and takes the form x^ := arg min_x ∥y−Ax∥_2 + λf(x), and has been analyzed in [1]. [1] further made conjectures about the performance of the generalized ℓ^2_2LASSO. This paper establishes these conjectures rigorously. We measure performance with the normalized squared error NSE(σ) := ∥x^−x_0∥^2_2/σ^2. Assuming the entries of A and v be i.i.d. standard normal, we precisely characterize the "asymptotic NSE" aNSE := lim_(σ→0)NSE(σ) when the problem dimensions m,n tend to infinity in a proportional manner. The role of λ,f and x_0 is explicitly captured in the derived expression via means of a single geometric quantity, the Gaussian distance to the subdifferential. We conjecture that aNSE=sup_(σ>0)NSE(σ). We include detailed discussions on the interpretation of our result, make connections to relevant literature and perform computational experiments that validate our theoretical findings.
Additional Information
© 2015 IEEE. The work of B. Hassibi was supported in part by the National Science Foundation under grants CNS0932428, CCF1018927, CCF1423663 and CCF1409204, by the Office of Naval Research under the MURI grant N0001408–0747, by the Jet Propulsion Lab under grant IA100076, by a grant from Qualcomm Inc., and by King Abdulaziz University.
Attached Files
Submitted  1502.06287v1.pdf
Files
Name  Size  Download all 

md5:287a2278b8b6318bb45e6a95386942e2

506.2 kB  Preview Download 
Additional details
 Eprint ID
 55292
 DOI
 10.1109/ISIT.2015.7282810
 Resolver ID
 CaltechAUTHORS:20150227070457225
 arXiv
 arXiv:1502.06287
 CNS0932428
 NSF
 CCF1018927
 NSF
 CCF1423663
 NSF
 CCF1409204
 NSF
 N0001408–0747
 Office of Naval Research (ONR)
 IA100076
 JPL
 Qualcomm Inc.
 King Abdulaziz University
 Created

20150306Created from EPrint's datestamp field
 Updated

20211110Created from EPrint's last_modified field