Minimax risk of matrix denoising by singular value thresholding

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 ${\min }_X\Vert Y-X{\Vert }_F^2/2+\lambda \Vert X{\Vert }_{\ast }$, where $\Vert X{\Vert }_{\ast }$ 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\to \rho$, $m_n/n\to \beta$), we evaluate the asymptotic minimax MSE $\mathcal{M}(\rho ,\beta )={\lim }_{m_n,n\to \infty }{\inf }_{\lambda }{\sup }_{\mathrm{rank}(X)\le r_n}\mathrm{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č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 }^{\ast }(\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.

Published in at http://dx.doi.org/10.1214/14-AOS1257 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
• Minimax risk of matrix denoising by singular value thresholding
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising

Cited by in corpus (39)

• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• Minimax risk of matrix denoising by singular value thresholding
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Statistical Inference, Learning and Models in Big Data
• The Optimal Hard Threshold for Singular Values is 4/sqrt(3)
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Sharp MSE Bounds for Proximal Denoising
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Optimal spectral shrinkage and PCA with heteroscedastic noise
• Singular vector and singular subspace distribution for the matrix denoising model
• Generalized SURE for optimal shrinkage of singular values in low-rank matrix denoising
• Robust angle-based transfer learning in high dimensions
• Near-optimal matrix recovery from random linear measurements
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Dynamic mode decomposition with control
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• Optimal Structured Principal Subspace Estimation: Metric Entropy and Minimax Rates
• A Schatten-$q$ Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound
• Degrees of Freedom Analysis of Unrolled Neural Networks
• Normal Approximation and Confidence Region of Singular Subspaces
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• High dimensional regression and matrix estimation without tuning parameters
• Tensor SVD: Statistical and Computational Limits
• Spectral State Compression of Markov Processes
• Adaptive Reduced Rank Regression
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• Adaptive Estimation of Noise Variance and Matrix Estimation via USVT Algorithm
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• Matrix Denoising with Partial Noise Statistics: Optimal Singular Value Shrinkage of Spiked F-Matrices
• Adaptive Shrinkage of singular values
• Optimal singular value shrinkage for operator norm loss
• Freeness over the diagonal and outliers detection in deformed random matrices with a variance profile
• An exact $\sin \Theta$ formula for matrix perturbation analysis and its applications
• Convolutional Imputation of Matrix Networks
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Sparse spectral estimation with missing and corrupted measurements
• Source Enumeration via RMT Estimator Based on Linear Shrinkage Estimation of Noise Eigenvalues Using Relatively Few Samples
• Optimal Estimation of Schatten Norms of a rectangular Matrix