Exponential Family Matrix Completion under Structural Constraints

We consider the matrix completion problem of recovering a structured matrix from noisy and partial measurements. Recent works have pro-posed tractable estimators with strong statistical guarantees for the case where the underlying ma-trix 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 ap-plications of matrix completion require estima-tors 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 mea-surements, and (c) heterogeneous structural con-straints beyond low–rank, such as block–sparsity, or a superposition structure of low–rank plus el-ementwise sparseness, among others. In this pa-per, we provide a vastly unified framework for generalized matrix completion by considering a matrix completion setting wherein the matrix en-tries are sampled from any member of the rich family of exponential family distributions; and impose general structural constraints on the un-derlying matrix, as captured by a general regu-larizer R(.). We propose a simple convex reg-ularized M–estimator for the generalized frame-work, and provide a unified and novel statistical analysis for this general class of estimators. We finally corroborate our theoretical results on sim-ulated datasets