MINIMAX RISK OF MATRIX DENOISING BY SINGULAR VALUE THRESHOLDING
成果类型：
Article
署名作者：
Donoho, David; Gavish, Matan
署名单位：
Stanford University
刊物名称：
ANNALS OF STATISTICS
ISSN/ISSBN：
0090-5364
DOI：
10.1214/14-AOS1257
发表日期：
2014
页码：
2413-2440
关键词：
摘要：
An unknown m by n matrix X-0 is to be estimated from noisy measurements Y = X-0 + Z, where the noise matrix Z has i.i.d. Gaussian entries. A popular matrix denoising scheme solves the nuclear norm penalization problem min(X) parallel to Y - X parallel to(2)(F)/2 + lambda parallel to X parallel to* where parallel to X parallel to(*) denotes the nuclear norm (sum of singular values). This is the analog, for matrices, of l(1) penalization in the vector case. It has been empirically observed that if X-0 has low rank, it may be recovered quite accurately from the noisy measurement Y. In a proportional growth framework where the rank r(n), number of rows m(n) and number of columns n all tend to infinity proportionally to each other (r(n)/m(n) -> rho, m(n)/n -> beta), we evaluate the asymptotic minimax MSE M (rho, beta) = lim(mn),n ->infinity inf(lambda) sup(rank(X)<= rn) MSE(X-0, (X) over cap). Our formulas involve incomplete moments of the quarter- and semi-circle laws (beta = 1, square case) and the Mareenko-Pastur law (beta < 1, nonsquare case). For finite m and n, we show that MSE increases as the nonzero singular values of X-0 grow larger. As a result, the finite-n worst-case MSE, a quantity which can be evaluated numerically, is achieved when the signal X-0 is infinitely strong. The nuclear norm penalization problem is solved by applying soft thresholding to the singular values of Y. We also derive the minimax threshold, namely the value lambda* (rho), which is the optimal place to threshold the singular values. All these results are obtained for general (nonsquare, nonsymmetric) real matrices. Comparable results are obtained for square symmetric nonnegative-definite matrices.