A Caltech Library Service

On a Relation between the Minimax Risk and the Phase Transitions of Compressed Recovery

Oymak, Samet and Hassibi, Babak (2012) On a Relation between the Minimax Risk and the Phase Transitions of Compressed Recovery. In: 2012 50th Annual Allerton Conference on Communication, Control, and Computing. IEEE , Piscataway, NJ, pp. 1018-1025. ISBN 978-1-4673-4537-8.

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

Use this Persistent URL to link to this item:


This paper provides a sharp analysis of the optimally tuned denoising problem and establishes a relation between the estimation error (minimax risk) and phase transition for compressed sensing recovery using convex and continuous functions. Phase transitions deal with recovering a signal xo from compressed linear observations Ax_0 by minimizing a certain convex function f(·). On the other hand, denoising is the problem of estimating a signal x_0 from noisy observations y = x_0+z using the regularization min_x λ/f(x) + 1/2∥y-x∥_2^2. In general, these problems are more meaningful and useful when the signal x_0 has a certain structure and the function f(·) is chosen to exploit this structure. Examples include, l_1 and l_1 - l_2 norms for sparse and block sparse vectors and nuclear norm for low rank matrices. In this work, we carefully analyze the minimax denoising problem and relate our results to the phase transition performance under a considerably general setting where the measurement A in compressed recovery and the noise z in the denoising problem are iid Gaussian random variables. Our results suggest that the required number of observations to recover a compressed signal is closely related to the asymptotic variance of the optimal estimation error. This relation was first empirically noted in [9]. Here we provide a rigorous foundation.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2012 IEEE. This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI)N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:compressed sensing, minimax risk, phase transitions, Gaussian width, generalized sparsity, proximity operator, convex optimization
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number13400740
Record Number:CaltechAUTHORS:20130731-085137179
Persistent URL:
Official Citation:Oymak, S.; Hassibi, B., "On a relation between the minimax risk and the phase transitions of compressed recovery," Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on , vol., no., pp.1018,1025, 1-5 Oct. 2012 doi: 10.1109/Allerton.2012.6483330
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:39666
Deposited By: Ruth Sustaita
Deposited On:31 Jul 2013 16:19
Last Modified:03 Oct 2019 05:09

Repository Staff Only: item control page