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: |
| ||||||||||||

ORCID: |
| ||||||||||||

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: |
| ||||||||||||

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