Exponential Family Matrix Completion under Structural Constraint

Suriya Gunasekar, Pradeep Ravikumar, Joydeep Ghosh

Abstract:   We consider the matrix completion problem of recovering a structured matrix from noisy and partial measurements. Recent works have proposed tractable estimators with strong statistical guarantees for the case where the underlying matrix is low-rank, and the measurements consist of a subset, either of the exact individual entries, or of the entries perturbed by additive Gaussian noise, which is thus implicitly suited for thin-tailed continuous data. Arguably, common applications of matrix completion require estimators for (a) heterogeneous data-types, such as skewed-continuous, count, binary, etc., (b) for heterogeneous noise models (beyond Gaussian), which capture varied uncertainty in the measurements, and (c) heterogeneous structural constraints beyond low-rank, such as block-sparsity, or a superposition structure of low-rank plus el-ementwise sparseness, among others. In this paper, we provide a vastly unified framework for generalized matrix completion by considering a matrix completion setting wherein the matrix entries are sampled from any member of the rich family of exponential family distributions; and impose general structural constraints on the underlying matrix, as captured by a general regu-larizer TZ(.). We propose a simple convex regularized M-estimator for the generalized framework, and provide a unified and novel statistical analysis for this general class of estimators. We finally corroborate our theoretical results on simulated datasets.

Download: pdf


  • Exponential Family Matrix Completion under Structural Constraint (pdf, software)
    S. Gunasekar, P. Ravikumar, J. Ghosh.
    In International Conference on Machine Learning (ICML), June 2014.