The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising

Let X0 be an unknown M by N matrix. In matrix recovery, one takes n < MN linear measurements y1,..., yn of X0, where yi = Tr(aTi X0) and each ai is a M by N matrix. For measurement matrices with Gaussian i.i.d entries, it known that if X0 is of low rank, it is recoverable from just a few measurements. A popular approach for matrix recovery is Nuclear Norm Minimization (NNM): solving the convex optimization problem min ‖X‖ ∗ subject to yi = Tr(aTi X) for all 1 ≤ i ≤ n, where ‖ · ‖ ∗ denotes the nuclear norm, namely, the sum of singular values. Empirical work reveals a phase transition curve, stated in terms of the undersampling fraction δ(n,M,N) = n/(MN), rank fraction ρ = r/N and aspect ratio β = M/N. Specifically, a curve δ ∗ = δ∗(ρ;β) exists such that, if δ> δ∗(ρ;β), NNM typically succeeds, while if δ < δ∗(ρ;β), it typically fails. An apparently quite different problem is matrix denoising in Gaus-sian noise, where an unknown M by N matrix X0 is to be estimated based on direct noisy measurements Y = X0 + Z, where the matrix Z has iid Gaussian entries. It has been empirically observed that, if X0 has low rank, it may be recovered quite accurately from the noisy measurement Y. A popular matrix denoising scheme solves the un-constrained optimization problem min ‖Y −X‖2F /2 + λ‖X‖∗. When optimally tuned, this scheme achieves the asymptotic minimax MSE M(ρ) = limN→ ∞ infλ suprank(X)≤ρ·N MSE(X, X̂λ)