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

David L. Donoho, Matan Gavish, Andrea Montanari

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$…