CaltechAUTHORS
  A Caltech Library Service

The squared-error of generalized LASSO: A precise analysis

Oymak, Samet and Thrampoulidis, Christos and Hassibi, Babak (2013) The squared-error of generalized LASSO: A precise analysis. In: 51st Annual Allerton Conference on Communication, Control, and Computing. IEEE , Piscataway, NJ, pp. 1002-1009. ISBN 978-1-4799-3410-2. https://resolver.caltech.edu/CaltechAUTHORS:20170201-142815906

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170201-142815906

Abstract

We consider the problem of estimating an unknown but structured signal x0 from its noisy linear observations y = Ax_0 + z ∈ ℝ^m. To the structure of x0 is associated a structure inducing convex function f(·). We assume that the entries of A are i.i.d. standard normal N(0, 1) and z ~ N(0, σ^2I_m). As a measure of performance of an estimate x^* of x_0 we consider the “Normalized Square Error” (NSE) ∥x* - x0∥^2_2/σ^2. For sufficiently small σ, we characterize the exact performance of two different versions of the well known LASSO algorithm. The first estimator is obtained by solving the problem arg min_x ∥y - Ax∥_2 + λf(x). As a function of λ, we identify three distinct regions of operation. Out of them, we argue that “RON” is the most interesting one. When λ ∈ R_(ON), we show that the NSE is (D_f(x_0, λ))/(m-D_f(x_0, λ)) for small σ, where D_f(x_0, λ) is the expected squared-distance of an i.i.d. standard normal vector to the dilated subdifferential λ · ∂f(x_0). Secondly, we consider the more popular estimator arg min_x 1/2∥y - Ax∥^2_2 + στ f(x). We propose a formula for the NSE of this estimator by establishing a suitable mapping between this and the previous estimator over the region RON. As a useful side result, we find explicit formulae for the optimal estimation performance and the optimal penalty parameters λ* and τ*.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/Allerton.2013.6736635DOIArticle
http://ieeexplore.ieee.org/document/6736635/PublisherArticle
ORCID:
AuthorORCID
Thrampoulidis, Christos0000-0001-9053-9365
Additional Information:© 2013 IEEE. This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CIF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by a grant from Qualcomm Inc.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
NSFCNS-0932428
NSFCIF-1018927
Office of Naval Research (ONR)N00014-08-1-0747
Qualcomm Inc.UNSPECIFIED
Record Number:CaltechAUTHORS:20170201-142815906
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170201-142815906
Official Citation:S. Oymak, C. Thrampoulidis and B. Hassibi, "The squared-error of generalized LASSO: A precise analysis," 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, 2013, pp. 1002-1009. doi: 10.1109/Allerton.2013.6736635
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73953
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:01 Feb 2017 22:51
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page