Provable Inductive Matrix Completion

By Prateek Jain, Inderjit S. Dhillon. 2013

184 citations recorded by the source corpus.

Consider a movie recommendation system where apart from the ratings information, side information such as user's age or movie's genre is also available. Unlike standard matrix completion, in this setting one should be able to predict inductively on new users/movies. In this paper, we study the problem of inductive matrix completion in the exact recovery setting. That is, we assume that the ratings matrix is generated by applying feature vectors to a low-rank matrix and the goal is to recover back the underlying matrix. Furthermore, we generalize the problem to that of low-rank matrix estimation using rank-1 measurements. We study this generic problem and provide conditions that the set of measurements should satisfy so that the alternating minimization method (which otherwise is a non-convex method with no convergence guarantees) is able to recover back the {\em exact} underlying low-rank matrix. In addition to inductive matrix completion, we show that two other low-rank estimation problems can be studied in our framework: a) general low-rank matrix sensing using rank-1 measurements, and b) multi-label regression with missing labels. For both the problems, we provide novel and interesting bounds on the number of measurements required by alternating minimization to provably converges to the {\em exact} low-rank matrix. In particular, our analysis for the general low rank matrix sensing problem significantly improves the required storage and computational cost than that required by the RIP-based matrix sensing methods \cite{RechtFP2007}. Finally, we provide empirical validation of our approach and demonstrate that alternating minimization is able to recover the true matrix for the above mentioned problems using a small number of measurements.

Subfields: Artificial Intelligence, Computational Mechanics, Control and Systems Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Control and Systems Engineering

Citations in the corpus

Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks (2017, methodology): “Classical Matrix Completion (MC) (Candes & Recht, 2012), Inductive Matrix Completion (IMC) (Jain & Dhillon, 2013; Xu et al., 2013), Geometric Matrix Completion (GMC) (Kalofolias et al., 2014), and Graph Reg-ularized Alternating Least Squares (GRALS) (Rao et al., 2015) were used as baseline methods.”
Predicting miRNA‐disease association based on inductive matrix completion (2018, methodology): “12 kA SdWHSmk 2 F is the least square cost function, k1 2 kWk 2 F and k2 2 kHk 2 F are set to overcome over-fitting problem, we can solved the minimum problem with a method proposed by Jain and Dhillon (2013). Firstly, we set W and H as random dense matrix, then we updated W and H using an iterative”
Dual-Primal Graph Convolutional Networks (2018, unknown): “MovieLens Flixster Douban Yahoo IMC [22, 45] 1.653 – – – GMC [24] 0.996 – – – MC [9] 0.973 – – – GRALS [39] 0”
Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction (2016, methodology): “Furthermore, when features are known for the time series, we can make use of interaction models such as those in [6, 24, 25].”
UvA-DARE ( Digital Academic Repository ) Graph Convolutional Matrix Completion (2017, unknown): “Inductive matrix completion (IMC) by Jain & Dhillon, 2013 and Xu et al., 2013 incorporates content information of users and items in feature vectors and approximates the observed elements of the rating matrix asMij = xTi UV T yj , with xi and yj representing the feature vector of user i and item j…”
Collaborative Filtering with Graph Information: Consistency and Scalable Methods (2015, methodology): “6 Experiments on Real Datasets Comparison to Related Formulations: We compare GRALS to other methods that incorporate side information for matrix completion: the ADMM method of [12] that regularizes the entire target matrix; using known features (IMC) [10, 24]; and standard matrix completion (MC).”
CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters (2017, methodology): “[15, 31] 1.653 GMC [16] 0.996 GRALS [26] 0.945 sRGCNN Cheby [24] 0.929 sRGCNN Cayley 0.922 Table 3: Test accuracy of different methods on the CORA dataset.”
Inductive matrix completion for predicting gene–disease associations (2014, methodology): “Next, we incorporate the features while trying to learn gene–disease associations in a novel inductive matrix completion (IMC) approach [recently developed and theoretically analyzed by Jain and Dhillon (2013)].”
Multitask Matrix Completion for Learning Protein Interactions Across Diseases (2016, unknown): “IMC (Jain and Dhillon, 2013; Natarajan and Dhillon, 2014): This is the link-prediction model from Section 2, in which data from all tasks are combined without incorporating any task relationships.”