The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
复制标题
DOI：
10.1073/pnas.1306110110
复制
发表时间：
2013-05-21
影响因子：
11.1
通讯作者：
Montanari, Andrea
中科院分区：
文献类型：
--
作者：
Donoho, David L.;Gavish, Matan;Montanari, Andrea
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 infinity)inf(lambda)sup(rank(X) 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.
