The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising

Let X-0 be an unknown M by N matrix. In matrix recovery, one takes n< MN linear measurements y1,., yn of X-0, where y(i) = Tr(A(i)(T)X(0)) and each A(i) is an M by N matrix. A popular approach for matrix recovery is nuclear norm minimization (NNM): solving the convex optimization problem min parallel to X parallel to(*) subject to y(i) = Tr(A(i)(T)X) for all 1 <= i <= n, where parallel to.parallel to(*) denotes the nuclear norm, namely, the sum of singular values. Empirical work reveals a phase transition curve, stated in terms of the undersampling fraction delta(n,M,N) = n/(MN), rank fraction rho= rank(X-0)/min{M,N}, and aspect ratio beta = M/N. Specifically when the measurement matrices A(i) have independent standard Gaussian random entries, a curve delta*(rho) = delta*(rho;beta) exists such that, if delta > delta*(rho), NNM typically succeeds for large M, N, whereas if delta < delta*(rho), it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, in which an unknown M by N matrix X-0 is to be estimated based on direct noisy measurements Y = X-0 + Z, where the matrix Z has independent and identically distributed Gaussian entries. A popular matrix denoising scheme solves the unconstrained optimization problem min parallel to Y-X parallel to(2)(F)/2 + lambda parallel to X parallel to(*). When optimally tuned, this scheme achieves the asymptotic minimax mean-squared error M(rho;beta) = lim(M,N ->infinity)inf(lambda)sup(rank(X)<=rho).MMSE(X,(X) over cap (lambda)), where M/N -> beta. We report extensive experiments showing that the phase transition delta*(rho) in the first problem, matrix recovery from Gaussian measurements, coincides with the minimax risk curve M(rho) = M(rho;beta) in the second problem, matrix denoising in Gaussian noise: delta*(rho) = M(rho), for any rank fraction 0 < rho < 1 (at each common aspect ratio beta). Our experiments considered matrices belonging to two constraint classes: real M by N matrices, of various ranks and aspect ratios, and real symmetric positive-semidefinite N by N matrices, of various ranks.