首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
  • 本地全文:下载
  • 作者:David L. Donoho ; Matan Gavish ; Andrea Montanari
  • 期刊名称: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.
  • 关键词:compressed sensing ; matrix completion
国家哲学社会科学文献中心版权所有