Minimax risk of matrix denoising by singular value thresholding

An unknown m by n matrix X₀ is to be estimated from noisy measurements Y=X₀+Z, where the noise matrix Z has i. i. d. Gaussian entries. A popular matrix denoising scheme solves the nuclear norm penalization problem minₗ\|Y-X\|₅^2/2+\|X\|*, where \|X\|* denotes the nuclear norm (sum of singular values). This is the analog, for matrices, of ₁ penalization in the vector case. It has been empirically observed that if X₀ has low rank, it may be recovered quite accurately from the noisy measurement Y. In a proportional growth framework where the rank r₍, number of rows m₍ and number of columns n all tend to proportionally to each other (r₍/m₍, m₍/n), we evaluate the asymptotic minimax MSE M (, ) =₌_₍, n _ₑ₀₍₊ (ₗ) ₑ_₍MSE (X₀, X_). Our formulas involve incomplete moments of the quarter- and semi-circle laws (=1, square case) and the Marčenko–Pastur law (<1, nonsquare case). For finite m and n, we show that MSE increases as the nonzero singular values of X₀ grow larger. As a result, the finite-n worst-case MSE, a quantity which can be evaluated numerically, is achieved when the signal X₀ 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 ^* (), 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.