Sharp MSE Bounds for Proximal Denoising

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 ${\sigma }^2$. We employ a structure-inducing convex function $f(\cdot )$ and solve ${\min }_x\{\frac{1}{2}\Vert y-x{\Vert }_2^2+\sigma \lambda f(x)\}$ to estimate $x_0$, for some $\lambda >0$. Common choices for $f(\cdot )$ include the ${\ell }_1$ norm for sparse vectors, the ${\ell }_1-{\ell }_2$ norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate $x^{\ast }$ is the normalized mean-squared-error $\text{NMSE}(\sigma )=\frac{\mathbb{E}\Vert x^{\ast }-x_0{\Vert }_2^2}{{\sigma }^2}$. We show that NMSE is maximized as $\sigma \to 0$ and we find the \emph{exact} worst case NMSE, which has a simple geometric interpretation: the mean-squared-distance of a standard normal vector to the $\lambda$-scaled subdifferential $\lambda \partial f(x_0)$. When $\lambda$ is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained denoising problem ${\min }_{f(x)\le f(x_0)}\{\Vert y-x{\Vert }_2\}$. The paper also connects these results to the generalized LASSO problem, in which, one solves ${\min }_{f(x)\le f(x_0)}\{\Vert y-Ax{\Vert }_2\}$ to estimate $x_0$ from noisy linear observations $y=A{x}_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. 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.

37 pages

References in corpus (15)

• Computational and Statistical Tradeoffs via Convex Relaxation
• Minimax risk of matrix denoising by singular value thresholding
• A quasi-Newton proximal splitting method
• A framework to characterize performance of LASSO algorithms
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Block-length dependent thresholds in block-sparse compressed sensing
• Living on the edge: Phase transitions in convex programs with random data
• Sparse Recovery of Positive Signals with Minimal Expansion
• Compressive Principal Component Pursuit
• Atomic norm denoising with applications to line spectral estimation
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Sharp recovery bounds for convex demixing, with applications
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• Guarantees of Total Variation Minimization for Signal Recovery

Cited by in corpus (9)

• On risk bounds in isotonic and other shape restricted regression problems
• A new perspective on least squares under convex constraint
• Compressed Sensing with Prior Information: Optimal Strategies, Geometry, and Bounds
• Tight convex relaxations for sparse matrix factorization
• On matrix estimation under monotonicity constraints
• Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO
• Sharp recovery bounds for convex demixing, with applications
• High dimensional regression and matrix estimation without tuning parameters
• Precise Phase Transition of Total Variation Minimization