A Caltech Library Service

Noisy estimation of simultaneously structured models: Limitations of convex relaxation

Oymak, Samet and Jalali, Amin and Fazel, Maryam and Hassibi, Babak (2013) Noisy estimation of simultaneously structured models: Limitations of convex relaxation. In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC). IEEE , Piscataway, NJ, pp. 6019-6024. ISBN 978-1-4673-5714-2.

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

Use this Persistent URL to link to this item:


Models or signals exhibiting low dimensional behavior (e.g., sparse signals, low rank matrices) play an important role in signal processing and system identification. In this paper, we focus on models that have multiple structures simultaneously; e.g., matrices that are both low rank and sparse, arising in phase retrieval, quadratic compressed sensing, and cluster detection in social networks. We consider the estimation of such models from observations corrupted by additive Gaussian noise. We provide tight upper and lower bounds on the mean squared error (MSE) of a convex denoising program that uses a combination of regularizers to induce multiple structures. In the case of low rank and sparse matrices, we quantify the gap between the MSE of the convex program and the best achievable error, and we present a simple (nonconvex) thresholding algorithm that outperforms its convex counterpart and achieves almost optimal MSE. This paper extends prior work on a different but related problem: recovering simultaneously structured models from noiseless compressed measurements, where bounds on the number of required measurements were given. The present work shows a similar fundamental limitation exists in a statistical denoising setting.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2013 IEEE. Research supported in part by the National Science Foundation Career award ECCS-0847077 and by the NSF grants CCF-0729203, CNS-0932428 and CCF-1018927.
Funding AgencyGrant Number
Subject Keywords:simultaneously structured, low rank and sparse, denoising, estimation, compressed sensing
Record Number:CaltechAUTHORS:20150224-071400977
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:55124
Deposited By: Shirley Slattery
Deposited On:27 Feb 2015 00:40
Last Modified:03 Oct 2019 08:03

Repository Staff Only: item control page