{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T16:58:59Z","timestamp":1791565139747,"version":"4.3.4"},"reference-count":25,"publisher":"Institute of Mathematical Statistics","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2014,12,1]]},"abstract":"<jats:p>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 $\\operatorname{min}_{X}\\|Y-X\\|_{F}^{2}\/2+\\lambda\\|X\\|_{*}$, where $\\|X\\|_{*}$ denotes the nuclear norm (sum of singular values). This is the analog, for matrices, of $\\ell_{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 $\\infty$ proportionally to each other ($r_{n}\/m_{n}\\rightarrow \\rho$, $m_{n}\/n\\rightarrow \\beta$), we evaluate the asymptotic minimax MSE $ \\mathcal{M} (\\rho,\\beta)=\\lim_{m_{n},n\\rightarrow \\infty}\\inf_{\\lambda}\\sup_{\\operatorname{rank}(X)\\leq r_{n}}\\operatorname{MSE}(X_{0},\\hat{X}_{\\lambda})$. Our formulas involve incomplete moments of the quarter- and semi-circle laws ($\\beta=1$, square case) and the Mar\u010denko\u2013Pastur law ($\\beta&lt;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 \u201cinfinitely strong.\u201d 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.<\/jats:p>","DOI":"10.1214\/14-aos1257","type":"journal-article","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T09:12:10Z","timestamp":1413796330000},"page":"2413-2440","source":"Crossref","is-referenced-by-count":79,"title":["Minimax risk of matrix denoising by singular value thresholding"],"prefix":"10.1214","volume":"42","author":[{"given":"David","family":"Donoho","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matan","family":"Gavish","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] Recht, B., Fazel, M. and Parrilo, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. <i>SIAM Rev.<\/i> <b>52<\/b> 471\u2013501.","DOI":"10.1137\/070697835"},{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] Anderson, T. W. (1955). The integral of a symmetric unimodal function over a symmetric convex set and some probability inequalities. <i>Proc. Amer. Math. Soc.<\/i> <b>6<\/b> 170\u2013176.","DOI":"10.1090\/S0002-9939-1955-0069229-1"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] Cand\u00e8s, E. J., Sing-Long, C. A. and Trzasko, J. D. (2013). Unbiased risk estimates for singular value thresholding and spectral estimators. <i>IEEE Trans. Signal Process.<\/i> <b>61<\/b> 4643\u20134657.","DOI":"10.1109\/TSP.2013.2270464"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] Das Gupta, S., Anderson, T. W. and Mudholkar, G. S. (1964). Monotonicity of the power functions of some tests of the multivariate linear hypothesis. <i>Ann. Math. Statist.<\/i> <b>35<\/b> 200\u2013205.","DOI":"10.1214\/aoms\/1177703742"},{"key":"4","unstructured":"[4] Donoho, D. L. and Gavish, M. (2013). Companion website for the article the phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising. Available at <a href=\"http:\/\/www.runmycode.org\/CompanionSite\/Site265\">http:\/\/www.runmycode.org\/CompanionSite\/Site265<\/a>."},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] Donoho, D. and Gavish, M. (2014). Supplement to \u201cMinimax risk of matrix denoising by singular value thresholding.\u201d <a href=\"DOI:10.1214\/14-AOS1257SUPP\">DOI:10.1214\/14-AOS1257SUPP<\/a>.","DOI":"10.1214\/14-AOS1257"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] Donoho, D. L., Gavish, M. and Montanari, A. (2013). The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising. <i>Proc. Natl. Acad. Sci. USA<\/i> <b>110<\/b> 8405\u20138410.","DOI":"10.1073\/pnas.1306110110"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] Donoho, D. L., Johnstone, I. and Montanari, A. (2013). Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising. <i>IEEE Trans. Inform. Theory<\/i> <b>59<\/b> 3396\u20133433.","DOI":"10.1109\/TIT.2013.2239356"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] Donoho, D. L. and Johnstone, I. M. (1994). Minimax risk overl $\\ell_p$-balls forl $\\ell_q$-error. <i>Probab. Theory Related Fields<\/i> <b>303<\/b> 277\u2013303.","DOI":"10.1007\/BF01199026"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] Donoho, D. L., Johnstone, I. M., Hoch, J. C. and Stern, A. S. (1992). Maximum entropy and the nearly black object. <i>J. R. Stat. Soc. Ser. B Stat. Methodol.<\/i> <b>54<\/b> 41\u201381.","DOI":"10.1111\/j.2517-6161.1992.tb01864.x"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] Gavish, M. and Donoho, D. L. (2014). The optimal hard threshold for singular values is $4\/\\sqrt3$. <i>IEEE Trans. Inform. Theory<\/i> <b>60<\/b> 5040\u20135053.","DOI":"10.1109\/TIT.2014.2323359"},{"key":"11","unstructured":"[11] Grant, M. and Boyd, S. P. (2010). CVX: Matlab software for disciplined convex programming, version 2.0 beta. Available at <a href=\"http:\/\/cvxr.com\/cvx\">http:\/\/cvxr.com\/cvx<\/a>, September 2013."},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] Koltchinskii, V., Lounici, K. and Tsybakov, A. B. (2011). Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. <i>Ann. Statist.<\/i> <b>39<\/b> 2302\u20132329.","DOI":"10.1214\/11-AOS894"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] Lewis, A. S. (1995). The convex analysis of unitarily invariant matrix functions. <i>J. Convex Anal.<\/i> <b>2<\/b> 173\u2013183.","DOI":"10.68381\/jca02012"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] Lewis, A. S. and Sendov, H. S. (2005). Nonsmooth analysis of singular values. I. Theory. <i>Set-Valued Var. Anal.<\/i> <b>13<\/b> 213\u2013241.","DOI":"10.1007\/s11228-004-7197-7"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Marcenko, V. and Pastur, L. (1967). Distribution of eigenvalues for some sets of random matrices. <i>Mathematics USSR Sbornik<\/i> <b>1<\/b> 457\u2013483.","DOI":"10.1070\/SM1967v001n04ABEH001994"},{"key":"16","unstructured":"[16] Oymak, S. and Hassibi, B. (2010). New null space results and recovery thresholds for matrix rank minimization. Preprint. Available at <a href=\"http:\/\/arxiv.org\/pdf\/1011.6326v1.pdf\">http:\/\/arxiv.org\/pdf\/1011.6326v1.pdf<\/a>."},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Oymak, S. and Hassibi, B. (2012). On a relation between the minimax risk and the phase transitions of compressed recovery. In 2012 50<i>th Annual Allerton Conference on Communication<\/i>, <i>Control<\/i>, <i>and Computing<\/i> 1018\u20131025. IEEE, Piscataway, NJ. Available at <a href=\"http:\/\/ieeexplore.ieee.org\/stamp\/stamp.jsp?arnumber=6483330\">http:\/\/ieeexplore.ieee.org\/stamp\/stamp.jsp?arnumber=6483330<\/a>.","DOI":"10.1109\/Allerton.2012.6483330"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] Recht, B., Xu, W. and Hassibi, B. (2011). Null space conditions and thresholds for rank minimization. <i>Math. Program.<\/i> <b>127<\/b> 175\u2013202.","DOI":"10.1007\/s10107-010-0422-2"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] Rohde, A. and Tsybakov, A. B. (2011). Estimation of high-dimensional low-rank matrices. <i>Ann. Statist.<\/i> <b>39<\/b> 887\u2013930.","DOI":"10.1214\/10-AOS860"},{"key":"22","unstructured":"[22] Shabalin, A. and Nobel, A. (2010). Reconstruction of a low-rank matrix in the presence of Gaussian noise. Preprint. Available at <a href=\"arXiv:1007.4148\">arXiv:1007.4148<\/a>."},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] Stein, C. M. (1981). Estimation of the mean of a multivariate normal distribution. <i>Ann. Statist.<\/i> <b>9<\/b> 1135\u20131151.","DOI":"10.1214\/aos\/1176345632"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] Tanner, J. and Wei, K. (2013). Normalized iterative hard thresholding for matrix completion. <i>SIAM J. Sci. Comput.<\/i> <b>35<\/b> S104\u2013S125.","DOI":"10.1137\/120876459"},{"key":"25","doi-asserted-by":"crossref","unstructured":"[25] Zanella, A., Chiani, M. and Win, M. Z. (2009). On the marginal distribution of the eigenvalues of Wishart matrices. <i>IEEE Transactions on Communications<\/i> <b>57<\/b> 1050\u20131060.","DOI":"10.1109\/TCOMM.2009.04.070143"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] Recht, B., Xu, W. and Hassibi, B. (2008). Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization. In <i>Proceedings of the<\/i> 47<i>th IEEE Conference on Decision and Control Cancun<\/i>, <i>Mexico<\/i>.","DOI":"10.1109\/CDC.2008.4739332"}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"http:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1413810732","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T16:47:35Z","timestamp":1791564455000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-42\/issue-6\/Minimax-risk-of-matrix-denoising-by-singular-value-thresholding\/10.1214\/14-AOS1257.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,1]]},"references-count":25,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2014,12,1]]}},"URL":"https:\/\/doi.org\/10.1214\/14-aos1257","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,1]]}}}