期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2013
卷号：110
期号：21
页码：8405-8410
DOI：10.1073/pnas.1306110110
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：Let [IMG]/medium/pnas.1306110110i1.gif" ALT="Formula "> be an unknown M by N matrix. In matrix recovery, one takes [IMG]/medium/pnas.1306110110i2.gif" ALT="Formula "> linear measurements [IMG]/medium/pnas.1306110110i3.gif" ALT="Formula "> of [IMG]/medium/pnas.1306110110i4.gif" ALT="Formula ">, where [IMG]/medium/pnas.1306110110i5.gif" ALT="Formula "> and each [IMG]/medium/pnas.1306110110i6.gif" ALT="Formula "> is an M by N matrix. A popular approach for matrix recovery is nuclear norm minimization (NNM): solving the convex optimization problem [IMG]/medium/pnas.1306110110i7.gif" ALT="Formula "> for all [IMG]/medium/pnas.1306110110i8.gif" ALT="Formula ">, where [IMG]/medium/pnas.1306110110i9.gif" ALT="Formula "> denotes the nuclear norm, namely, the sum of singular values. Empirical work reveals a phase transition curve, stated in terms of the undersampling fraction [IMG]/medium/pnas.1306110110i10.gif" ALT="Formula ">, rank fraction [IMG]/medium/pnas.1306110110i11.gif" ALT="Formula ">, and aspect ratio [IMG]/medium/pnas.1306110110i12.gif" ALT="Formula ">. Specifically when the measurement matrices Ai have independent standard Gaussian random entries, a curve [IMG]/medium/pnas.1306110110i13.gif" ALT="Formula "> exists such that, if [IMG]/medium/pnas.1306110110i14.gif" ALT="Formula ">, NNM typically succeeds for large M,N, whereas if [IMG]/medium/pnas.1306110110i15.gif" ALT="Formula ">, it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, in which an unknown M by N matrix [IMG]/medium/pnas.1306110110i16.gif" ALT="Formula "> is to be estimated based on direct noisy measurements [IMG]/medium/pnas.1306110110i17.gif" ALT="Formula ">, where the matrix Z has independent and identically distributed Gaussian entries. A popular matrix denoising scheme solves the unconstrained optimization problem [IMG]/medium/pnas.1306110110i18.gif" ALT="Formula ">. When optimally tuned, this scheme achieves the asymptotic minimax mean-squared error [IMG]/medium/pnas.1306110110i19.gif" ALT="Formula ">, where [IMG]/medium/pnas.1306110110i20.gif" ALT="Formula ">. We report extensive experiments showing that the phase transition [IMG]/medium/pnas.1306110110i21.gif" ALT="Formula "> in the first problem, matrix recovery from Gaussian measurements, coincides with the minimax risk curve [IMG]/medium/pnas.1306110110i22.gif" ALT="Formula "> in the second problem, matrix denoising in Gaussian noise: [IMG]/medium/pnas.1306110110i23.gif" ALT="Formula ">, for any rank fraction [IMG]/medium/pnas.1306110110i24.gif" ALT="Formula "> (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.
