The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising

Abstract

Let $X_0$ be an unknown $M$ by $N$ matrix. In matrix recovery, one takes $n<MN$ linear measurements $y_1,...,y_n$ of $X_0$, where $y_i = \Tr(a_i^T X_0)$ and each $a_i$ is a $M$ by $N$ matrix. For measurement matrices with Gaussian i.i.d entries, it known that if $X_0$ is of low rank, it is recoverable from just a few measurements. A popular approach for matrix recovery is Nuclear Norm Minimization (NNM). Empirical work reveals a \emph{phase transition} curve, stated in terms of the undersampling fraction $\delta (n,M,N)=n/(MN)$, rank fraction $\rho =r/N$ and aspect ratio $\beta =M/N$. Specifically, a curve ${\delta }^{\ast }={\delta }^{\ast }(\rho ;\beta )$ exists such that, if $\delta >{\delta }^{\ast }(\rho ;\beta )$, NNM typically succeeds, while if $\delta <{\delta }^{\ast }(\rho ;\beta )$, it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, where an unknown $M$ by $N$ matrix $X_0$ is to be estimated based on direct noisy measurements $Y=X_0+Z$, where the matrix $Z$ has iid Gaussian entries. It has been empirically observed that, if $X_0$ has low rank, it may be recovered quite accurately from the noisy measurement $Y$. A popular matrix denoising scheme solves the unconstrained optimization problem $\text{min}\Vert Y-X{\Vert }_F^2/2+\lambda \Vert X{\Vert }_{\ast }$. When optimally tuned, this scheme achieves the asymptotic minimax MSE $\cM(ρ) = \lim_{N \goto \infty} \inf_λ\sup_{\rank(X) \leq ρ\cdot N} MSE(X,\hat{X}_λ)$. We report extensive experiments showing that the phase transition ${\delta }^{\ast }(\rho )$ in the first problem coincides with the minimax risk curve $\cM(ρ)$ in the second problem, for {\em any} rank fraction $0<\rho <1$.

References in corpus (3)

• Universality in polytope phase transitions and message passing algorithms
• 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

Cited by in corpus (20)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• 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
• Single-pixel imaging with origami pattern construction
• Statistical Inference, Learning and Models in Big Data
• Symmetry breaking gives rise to energy spectra of three states of matter
• Living on the edge: Phase transitions in convex programs with random data
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
• Sharp MSE Bounds for Proximal Denoising
• Near-optimal matrix recovery from random linear measurements
• Phase diagram of matrix compressed sensing
• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• Implicit Regularization and Convergence for Weight Normalization
• High dimensional regression and matrix estimation without tuning parameters
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Ranking Recovery from Limited Comparisons using Low-Rank Matrix Completion
• Phase Transition of Convex Programs for Linear Inverse Problems with Multiple Prior Constraints
• On Simplicity and Complexity in the Brave New World of Large-Scale Neuroscience
• Joint Beamforming and Phase Optimization in a Multi-user Communication System Composed of Dual Reconfigurable Intelligent Surfaces