Unified view of matrix completion under general structural constraints

Suriya Gunasekar, Arindam Banerjee, Joydeep Ghosh

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations


In this paper, we present a unified analysis of matrix completion under general low-dimensional structural constraints induced by any norm regularization. We consider two estimators for the general problem of structured matrix completion, and provide unified upper bounds on the sample complexity and the estimation error. Our analysis relies on results from generic chaining, and we establish two intermediate results of independent interest: (a) in characterizing the size or complexity of low dimensional subsets in high dimensional ambient space, a certain partial complexity measure encountered in the analysis of matrix completion problems is characterized in terms of a well understood complexity measure of Gaussian widths, and (b) it is shown that a form of restricted strong convexity holds for matrix completion problems under general norm regularization. Further, we provide several non-trivial examples of structures included in our framework, notably the recently proposed spectral k-support norm.

Original languageEnglish (US)
Pages (from-to)1180-1188
Number of pages9
JournalAdvances in Neural Information Processing Systems
StatePublished - 2015
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: Dec 7 2015Dec 12 2015

Bibliographical note

Funding Information:
We thank the anonymous reviewers for helpful comments and suggestions. S. Gunasekar and J. Ghosh acknowledge funding from NSF grants IIS-1421729, IIS-1417697, and IIS1116656. A. Banerjee acknowledges NSF grants IIS-1447566, IIS-1422557, CCF-1451986, CNS-1314560, IIS-0953274, IIS-1029711, and NASA grant NNX12AQ39A.


Dive into the research topics of 'Unified view of matrix completion under general structural constraints'. Together they form a unique fingerprint.

Cite this