Sharp MSE Bounds for Proximal Denoising
 Creators
 Oymak, Samet
 Hassibi, Babak
Abstract
Denoising has to do with estimating a signal x_0 from its noisy observations y = x_0 + z. In this paper, we focus on the "structured denoising problem," where the signal x_0 possesses a certain structure and z has independent normally distributed entries with mean zero and variance σ^2. We employ a structureinducing convex function f(⋅) and solve min_x {1/2 ∥y−x∥^2_2 +σλf(x)}to estimate x_0, for some λ>0. Common choices for f(⋅) include the ℓ_1 norm for sparse vectors, the ℓ_1 −ℓ_2 norm for blocksparse signals and the nuclear norm for lowrank matrices. The metric we use to evaluate the performance of an estimate x∗ is the normalized meansquared error NMSE(σ)=E∥x∗ − x_0∥^2_2/σ^2. We show that NMSE is maximized as σ→0 and we find the exact worstcase NMSE, which has a simple geometric interpretation: the meansquared distance of a standard normal vector to the λscaled subdifferential λ∂f(x_0). When λ is optimally tuned to minimize the worstcase NMSE, our results can be related to the constrained denoising problem min_(f(x)≤f(x_0)){∥y−x∥2}. The paper also connects these results to the generalized LASSO problem, in which one solves min_(f(x)≤f(x_0)){∥y−Ax∥2} to estimate x_0 from noisy linear observations y=Ax_0 + z. We show that certain properties of the LASSO problem are closely related to the denoising problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a "phase transition" as a function of number of observations. We also provide an orderoptimal bound for the LASSO error in terms of the meansquared distance. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the denoising and linear inverse problems.
Additional Information
© 2015 SFoCM. Received 13 November 2013; Revised 30 March 2015; Accepted 15 April 2015; First Online: 06 October 2015. This work was supported in part by the National Science Foundation under grants CCF0729203, CNS0932428 and CIF1018927, by the Office of Naval Research under the MURI grant N000140810747, and by a grant from Qualcomm Inc.Attached Files
Submitted  1305.2714v5.pdf
Files
Name  Size  Download all 

md5:d66840ac5f6c8c1ba45f0878016a1cb3

1.2 MB  Preview Download 
Additional details
 Alternative title
 Asymptotically Exact Denoising in Relation to Compressed Sensing
 Eprint ID
 69930
 DOI
 10.1007/s1020801592784
 Resolver ID
 CaltechAUTHORS:20160825102038882
 CCF0729203
 NSF
 CNS0932428
 NSF
 CIF1018927
 NSF
 N000140810747
 Office of Naval Research (ONR)
 Qualcomm Inc.
 Created

20160825Created from EPrint's datestamp field
 Updated

20230411Created from EPrint's last_modified field