Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow

Matrix completion method has been used in a wide range of applications such as collaborative filtering for recommendation (Koren et al., 2009), multi-label learning (Cabral et al., 2011) and clustering (Hsieh et al., 2012). In these applications, every entry is modeled as the inner product between factors corresponding to the row and column variables. For example, in movie recommendation, each row factor represents the latent representation of a user and each column factor represents the latent representation of a movie. In many applications of significant interest, besides the partially observed matrix, side information, in the form of features, is also available. These might correspond to demographic information (genders, occupation) for users or product information (genre, director) in a movie recommender system for example. With such features at hand, one can model an observation as a specific linear interaction between features to reduce the model complexity.