# Minimax risk of matrix denoising by singular value thresholding

Research paper by **David Donoho, Matan Gavish**

Indexed on: **04 Nov '14**Published on: **04 Nov '14**Published in: **Mathematics - Statistics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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\v{c}enko-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.