A Caltech Library Service

Simple Error Bounds for Regularized Noisy Linear Inverse Problems

Thrampoulidis, Christos and Oymak, Samet and Hassibi, Babak (2014) Simple Error Bounds for Regularized Noisy Linear Inverse Problems. In: 2014 IEEE International Symposium on Information Theory (ISIT),. IEEE , Piscataway, NJ, pp. 3007-3011. ISBN 978-1-4799-5186-4.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Consider estimating a structured signal x_0 from linear, underdetermined and noisy measurements y = Ax_0+z, via solving a variant of the lasso algorithm: x̂ = arg min_x{∥y-Ax∥+2 + λf(x)}. Here, f is a convex function aiming to promote the structure of x_0, say ℓ_1-norm to promote sparsity or nuclear norm to promote low-rankness. We assume that the entries of A are independent and normally distributed and make no assumptions on the noise vector z, other than it being independent of A. Under this generic setup, we derive a general, non-asymptotic and rather tight upper bound on the ℓ_2-norm of the estimation error ∥x̂ - x0∥2. Our bound is geometric in nature and obeys a simple formula; the roles of λ, f and x_0 are all captured by a single summary parameter δ(λ∂f(x_0)), termed the Gaussian squared distance to the scaled subdifferential. We connect our result to the literature and verify its validity through simulations.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Thrampoulidis, Christos0000-0001-9053-9365
Additional Information:© 2014 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.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Record Number:CaltechAUTHORS:20150121-071420813
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53909
Deposited By: Shirley Slattery
Deposited On:22 Jan 2015 21:27
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page