Asymptotically Exact Error Analysis for the Generalized ℓ^2_2-LASSO
Abstract
Given an unknown signal x_0∈R^n and linear noisy measurements y=Ax_0 + σv ∈ ℝ^m, the generalized ℓ^2_2-LASSO solves x^:=arg min_x 1/2∥y−Ax∥^2_2 + σλf(x). Here, f is a convex regularization function (e.g. ℓ_1-norm, nuclear-norm) aiming to promote the structure of x_0 (e.g. sparse, low-rank), and, λ ≥ 0 is the regularizer parameter. A related optimization problem, though not as popular or well-known, is often referred to as the generalized ℓ_2-LASSO 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_2-LASSO. 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 CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by the Office of Naval Research under the MURI grant N00014-08–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
- Resolver ID
- CaltechAUTHORS:20150227-070457225
- NSF
- CNS-0932428
- NSF
- CCF-1018927
- NSF
- CCF-1423663
- NSF
- CCF-1409204
- Office of Naval Research (ONR)
- N00014-08–0747
- JPL
- IA100076
- Qualcomm Inc.
- King Abdulaziz University
- Created
-
2015-03-06Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field