Abstract
Let be an unknown by matrix. In matrix recovery, one takes linear measurements of , where $y_i = \Tr(a_i^T X_0)$ and each is a by matrix. For measurement matrices with Gaussian i.i.d entries, it known that if 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 , rank fraction and aspect ratio . Specifically, a curve exists such that, if , NNM typically succeeds, while if , it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, where an unknown by matrix is to be estimated based on direct noisy measurements , where the matrix has iid Gaussian entries. It has been empirically observed that, if has low rank, it may be recovered quite accurately from the noisy measurement . A popular matrix denoising scheme solves the unconstrained optimization problem . 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 in the first problem coincides with the minimax risk curve $\cM(ρ)$ in the second problem, for {\em any} rank fraction .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.