Timezone: »

 
Poster
Unified View of Matrix Completion under General Structural Constraints
Suriya Gunasekar · Arindam Banerjee · Joydeep Ghosh

Thu Dec 10 08:00 AM -- 12:00 PM (PST) @ 210 C #87
in Poster Session »
Matrix completion problems have been widely studied under special low dimensional structures such as low rank or structure induced by decomposable norms. In this paper, we present a unified analysis of matrix completion under general low-dimensional structural constraints induced by {\em 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 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 \textit{\modified}~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 including the recently proposed spectral $k$-support norm.
[ PDF] 

Author Information

Suriya Gunasekar (UT Austin)
Arindam Banerjee (University of Minnesota)

Arindam Banerjee is a Professor at the Department of Computer & Engineering and a Resident Fellow at the Institute on the Environment at the University of Minnesota, Twin Cities. His research interests are in machine learning, data mining, and applications in complex real-world problems in different areas including climate science, ecology, recommendation systems, text analysis, and finance. He has won several awards, including the NSF CAREER award (2010), the IBM Faculty Award (2013), and six best paper awards in top-tier conferences.

Joydeep Ghosh (UT Austin)

More from the Same Authors