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.
https://resolver.caltech.edu/CaltechAUTHORS:20130731-085137179

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

## Abstract

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

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

Funders: |
| ||||||||||||

Subject Keywords: | compressed sensing, minimax risk, phase transitions, Gaussian width, generalized sparsity, proximity operator, convex optimization | ||||||||||||

Other Numbering System: |
| ||||||||||||

Record Number: | CaltechAUTHORS:20130731-085137179 | ||||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20130731-085137179 | ||||||||||||

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

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | Ruth Sustaita | ||||||||||||

Deposited On: | 31 Jul 2013 16:19 | ||||||||||||

Last Modified: | 03 Oct 2019 05:09 |

Repository Staff Only: item control page