Provable Inductive Matrix Completion

Abstract

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.

References in corpus (1)

• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint

Cited by in corpus (37)

• Graph Convolutional Matrix Completion
• Progresses and Challenges in Link Prediction
• PU Learning for Matrix Completion
• Dual-Primal Graph Convolutional Networks
• Inductive Matrix Completion Based on Graph Neural Networks
• High-dimensional Time Series Prediction with Missing Values
• A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing
• Orthogonal Inductive Matrix Completion
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
• Multi-weight Nuclear Norm Minimization for Low-rank Matrix Recovery in Presence of Subspace Prior Information
• Tensor train completion: local recovery guarantees via Riemannian optimization
• Generalization error bounds for kernel matrix completion and extrapolation
• Item Graph Convolution Collaborative Filtering for Inductive Recommendations
• Convolutional Geometric Matrix Completion
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Note: low-rank tensor train completion with side information based on Riemannian optimization
• Nonconvex One-bit Single-label Multi-label Learning
• A Greedy Algorithm for Matrix Recovery with Subspace Prior Information
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• Sparse Group Inductive Matrix Completion
• The Second Order Linear Model
• Noisy Inductive Matrix Completion Under Sparse Factor Models
• Regret Bounds for Non-decomposable Metrics with Missing Labels
• Matrix Completion via Factorizing Polynomials
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Inductive Matrix Completion Using Graph Autoencoder
• Matrix Completion with Side Information using Manifold Optimization
• Sample Efficient Linear Meta-Learning by Alternating Minimization
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees
• Image Tag Completion and Refinement by Subspace Clustering and Matrix Completion
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Variational Bayesian inference for CP tensor completion with side information
• Multi-weight Matrix Completion with Arbitrary Subspace Prior Information
• Subspace Clustering Based Tag Sharing for Inductive Tag Matrix Refinement with Complex Errors
• Simple and Powerful Architecture for Inductive Recommendation Using Knowledge Graph Convolutions
• Generating Artificial Core Users for Interpretable Condensed Data
• Collaborative Self-Attention for Recommender Systems