CaltechAUTHORS
  A Caltech Library Service

Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information

Oymak, Samet and Thrampoulidis, Christos and Hassibi, Babak (2013) Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20150121-072935827

[img] PDF - Submitted Version
See Usage Policy.

234Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150121-072935827

Abstract

This paper considers the linear inverse problem where we wish to estimate a structured signal x_0 from its corrupted observations. When the problem is ill-posed, it is natural to associate a convex function f(·) with the structure of the signal. For example, ℓ_1 norm can be used for sparse signals. To carry out the estimation, we consider two well-known convex programs: 1) Second order cone program (SOCP), and, 2) Lasso. Assuming Gaussian measurements, we show that, if precise information about the value f(x_0) or the ℓ_2-norm of the noise is available, one can do a particularly good job at estimation. In particular, the reconstruction error becomes proportional to the “sparsity” of the signal rather than to the ambient dimension of the noise vector. We connect our results to the existing literature and provide a discussion on their relation to the standard least-squares problem. Our error bounds are non-asymptotic and sharp, they apply to arbitrary convex functions and do not assume any distribution on the noise.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1312.0641arXivDiscussion Paper
Additional Information: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
Subject Keywords:sparse estimation, convex optimization, Lasso, structured signals, Gaussian width, model selection, linear inverse
Record Number:CaltechAUTHORS:20150121-072935827
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150121-072935827
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53911
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:23 Jan 2015 00:52
Last Modified:23 Jan 2015 00:52

Repository Staff Only: item control page