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

preprint2013arXivOpen access

Abstract

Let X0X_0 be an unknown MM by NN matrix. In matrix recovery, one takes n<MNn < MN linear measurements y1,...,yny_1,..., y_n of X0X_0, where $y_i = \Tr(a_i^T X_0)$ and each aia_i is a MM by NN matrix. For measurement matrices with Gaussian i.i.d entries, it known that if X0X_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 δ(n,M,N)=n/(MN)δ(n,M,N) = n/(MN), rank fraction ρ=r/Nρ=r/N and aspect ratio β=M/Nβ=M/N. 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 MM by NN matrix X0X_0 is to be estimated based on direct noisy measurements Y=X0+ZY = X_0 + Z, where the matrix ZZ has iid Gaussian entries. It has been empirically observed that, if X0X_0 has low rank, it may be recovered quite accurately from the noisy measurement YY. A popular matrix denoising scheme solves the unconstrained optimization problem min∥Y−X∥F2/2+λ∥X∥∗\text{min} \| Y - X \|_F^2/2 + λ\|X\|_* . 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 0<ρ<10 < ρ< 1.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.