11/20/2015

Post date: Nov 30, 2015 7:40:18 PM

Title: Matrix completion with nearly optimal bounds on sample complexity

Speaker: Tingni Sun, Department of Mathematics, University of Maryland, College Park

Abstract:

This talk concerns the problem of matrix completion, which is to estimate a matrix from observations in a small subset of indices. We first study the nuclear norm minimization with the restriction of matching the uncorrupted observations. Under certain coherence conditions, it is shown that the required sample size is of nearly optimal order via a novel graphical approach. The procedure is then extended to the case of noisy observations. We propose a calibrated spectrum elastic net method with a sum of the nuclear and Frobenius penalties and develop an iterative algorithm to solve the convex minimization problem. Under coherence conditions and for proper penalties levels, the proposed estimator achieves an error bound of nearly optimal order and in proportion to the noise level. This provides a unified analysis of the noisy and noiseless matrix completion problems. Simulation results will be discussed to compare our proposal with some existing methods.