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

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 x(0) 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) lambda(f) (x) + 1/2 parallel to y - x parallel to(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.