Poster
Mixture Matrix Completion
Daniel Pimentel-Alarcon
Room 210 #88
Keywords: [ Video Segmentation ] [ Tracking and Motion in Video ] [ Missing Data ] [ Signal Processing ] [ Recommender Systems ] [ Collaborative Filtering ] [ Non-Convex Optimization ] [ Network Analysis ] [ Matrix and Tensor Factorization ] [ Components Analysis (e.g., CCA, ICA, LDA, PCA) ] [ Image Segmentation ] [ Classification ] [ Sparsity and Compressed Sensing ] [ Computer Vision ] [ Combinatorial Optimization ] [ Information Theory ] [ Clustering ]
Completing a data matrix X has become an ubiquitous problem in modern data science, with motivations in recommender systems, computer vision, and networks inference, to name a few. One typical assumption is that X is low-rank. A more general model assumes that each column of X corresponds to one of several low-rank matrices. This paper generalizes these models to what we call mixture matrix completion (MMC): the case where each entry of X corresponds to one of several low-rank matrices. MMC is a more accurate model for recommender systems, and brings more flexibility to other completion and clustering problems. We make four fundamental contributions about this new model. First, we show that MMC is theoretically possible (well-posed). Second, we give its precise information-theoretic identifiability conditions. Third, we derive the sample complexity of MMC. Finally, we give a practical algorithm for MMC with performance comparable to the state-of-the-art for simpler related problems, both on synthetic and real data.
Live content is unavailable. Log in and register to view live content