Adapting to Unknown Noise Distribution in Matrix Denoising

Abstract

We consider the problem of estimating an unknown matrix $\mathbf{X}\in {\mathbb{R}}^{m\times n}$, from observations $\mathbf{Y}=\mathbf{X}+\mathbf{W}$ where $\mathbf{W}$ is a noise matrix with independent and identically distributed entries, as to minimize estimation error measured in operator norm. Assuming that the underlying signal $\mathbf{X}$ 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{I_W}$ in the high-dimensional limit $m,n\to \infty$, where $I_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 $\mathbf{X}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{\mathsf{T}}$ --where $\mathbf{U}\in {\mathbb{R}}^{m\times r}$, $\mathbf{V}\in {\mathbb{R}}^{n\times r}$ are orthogonal, and $r$ is kept fixed as $m,n\to \infty$-- we use our method to estimate $\mathbf{U}$, $\mathbf{V}$. Standard spectral methods provide non-trivial estimates of the factors $\mathbf{U},\mathbf{V}$ (weak recovery) only if the singular values of $\mathbf{X}$ are larger than $(mn{)}^{1/4}\mathrm{Var}(W_{11}{)}^{1/2}$. We prove that the new approach achieves weak recovery down to the the information-theoretically optimal threshold $(mn{)}^{1/4}{I}_W^{1/2}$.

References in corpus (8)

• Matrix estimation by Universal Singular Value Thresholding
• Asymptotic power of sphericity tests for high-dimensional data
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Localization from Incomplete Noisy Distance Measurements
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• High dimensional deformed rectangular matrices with applications in matrix denoising

Cited by in corpus (4)

• Inference for Heteroskedastic PCA with Missing Data
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Detection of Signal in the Spiked Rectangular Models
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise