Adapting to Unknown Noise Distribution in Matrix Denoising

We consider the problem of estimating an unknown matrix boldsymbolX∈ mathbb Rm× n, from observations boldsymbolY = boldsymbolX+boldsymbolW where boldsymbolW is a noise matrix with independent and identically distributed entries, as to minimize estimation error measured in operator norm. Assuming that the underlying signal boldsymbolX is low-rank and incoherent with respect to the canonical basis, we prove that minimax risk is equivalent to (√mvee√n)/√IW in the high-dimensional limit m,n→∞, where IW is the Fisher information of the noise. Crucially, we develop an efficient procedure that achieves this risk, adaptively over the noise distribution (under certain regularity assumptions). Letting boldsymbolX = boldsymbolUboldsymbolSigmaboldsymbolV^sf T --where boldsymbolU∈ mathbb Rm× r, boldsymbolV∈mathbb Rn× r are orthogonal, and r is kept fixed as m,n→∞-- we use our method to estimate boldsymbolU, boldsymbolV. Standard spectral methods provide non-trivial estimates of the factors boldsymbolU,boldsymbolV (weak recovery) only if the singular values of boldsymbolX are larger than (mn)1/4rm Var(W11)1/2. We prove that the new approach achieves weak recovery down to the the information-theoretically optimal threshold (mn)1/4IW1/2.