title: The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising.
abstract: Let X(0) be an unknown M by N matrix. In matrix recovery, one takes n < MN linear measurements y(1),…,y(n) of X(0), where y(i) = Tr(A(T)iX(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 ||X||*subject to y(i) =Tr(A(T)(i)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 ρ=rank(X0)/min {M,N}, and aspect ratio β=M/N. Specifically when the measurement matrices Ai have independent standard Gaussian random entries, a curve δ*(ρ) = δ*(ρ;β) exists such that, if δ > δ*(ρ), NNM typically succeeds for large M,N, whereas if δ < δ*(ρ), 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|| Y-X||(2)(F)/2+λ||X||*. When optimally tuned, this scheme achieves the asymptotic minimax mean-squared error M(ρ;β) = lim(M,N → ∞)inf(λ)sup(rank(X) ≤ ρ · M)MSE(X,X(λ)), where M/N → . We report extensive experiments showing that the phase transition δ*(ρ) in the first problem, matrix recovery from Gaussian measurements, coincides with the minimax risk curve M(ρ)=M(ρ;β) in the second problem, matrix denoising in Gaussian noise: δ*(ρ)=M(ρ), for any rank fraction 0 < ρ < 1 (at each common aspect ratio β). 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.
authors: Departments of Statistics and Electrical Engineering, Stanford University, Stanford, CA 94305, USA. donoho@stat.stanford.edu
authors: David L
authors: DL
authors: Donoho
authors: Matan
authors: M
authors: Gavish
authors: Andrea
authors: A
authors: Montanari
keywords: compressed sensing; matrix completion
references: Biometrics. 1990 Sep;46(3):737-48
references: 2242412
references: Proc Natl Acad Sci U S A. 2009 Nov 10;106(45):18914-9
references: 19858495
references: Proc Natl Acad Sci U S A. 2013 Jan 22;110(4):1181-6
references: 23277588
references: Proc Natl Acad Sci U S A. 2005 Jul 5;102(27):9452-7
references: 15972808
references: Phys Rev Lett. 2010 Oct 8;105(15):150401
references: 21230876
references: Philos Trans A Math Phys Eng Sci. 2009 Nov 13;367(1906):4273-93
references: 19805445