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

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.

Additional details