We consider the problem of estimating an unknown matrix $\bX\in \reals^{m\times n}$, from observations $\bY = \bX+\bW$ where $\bW$ is a noise matrix with independent and identically distributed entries, as to minimize estimation error measured in operator norm. Assuming that the underlying signal $\bX$ is low-rank and incoherent with respect to the canonical basis, we prove that minimax risk is equivalent to $(\sqrt{m}\vee\sqrt{n})/\sqrt{\Info_W}$ in the high-dimensional limit $m,n\to\infty$, where $\Info_W$ 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 $\bX = \bU\bSigma\bV^{\sT}$ --where $\bU\in \reals^{m\times r}$, $\bV\in\reals^{n\times r}$ are orthogonal, and $r$ is kept fixed as $m,n\to\infty$-- we use our method to estimate $\bU$, $\bV$. Standard spectral methods provide non-trivial estimates of the factors $\bU,\bV$ (weak recovery 查看全文>>