Provable Inductive Matrix Completion

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.

• Publication year

  2013

• Venue

  arXiv.org

• Publication date

  2013-06-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1306.0626
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages

  2013cited by this paper
• Low-rank matrix completion using alternating minimization

  2012influential reference
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions

  2011cited by this paper
• User-Friendly Tail Bounds for Sums of Random Matrices

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

  2009cited by this paper
• Matrix completion from a few entries

  2009cited by this paper
• The Power of Convex Relaxation: Near-Optimal Matrix Completion

  2009cited by this paper
• Guaranteed Rank Minimization via Singular Value Projection

  2009cited by this paper
• Robust principal component analysis?

  2009cited by this paper
• Sparse and low-rank matrix decompositions

  2009cited by this paper
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis

  2009cited by this paper
• A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization

  2008cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  2007influential reference
• On perturbations of matrix pencils with real spectra

  1994cited by this paper

• CGAF-SDP:A Species Distribution Prediction Model Based on Cross Graph Attention Fusion

  2025cites this paper
• Robust Tensor Completion With Side Information

  2025cites this paper
• Group-Sparse Inductive Matrix Completion Through Transfer Learning

  2025influential citation
• Differential Privacy of Quantum and Quantum-Inspired-Classical Recommendation Algorithms

  2025cites this paper
• Adaptively-weighted Nearest Neighbors for Matrix Completion

  2025cites this paper
• Handling new users and items: a comparative study of inductive recommenders

  2025cites this paper
• One Rank at a Time: Cascading Error Dynamics in Sequential Learning

  2025cites this paper
• Subspace-Informed Matrix Completion

  2024cites this paper
• Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders

  2024cites this paper
• Mixed Matrix Completion in Complex Survey Sampling under Heterogeneous Missingness

  2024cites this paper
• Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits

  2024cites this paper
• SADR: Self-Supervised Graph Learning With Adaptive Denoising for Drug Repositioning

  2024cites this paper
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems

  2024cites this paper
• Predicting miRNA-disease association based on Hybrid Graph Autoencoder

  2024cites this paper
• Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion

  2024cites this paper
• MoRGH: movie recommender system using GNNs on heterogeneous graphs

  2024cites this paper
• QM-RGNN: An Efficient Online QoS Measurement Framework with Sparse Matrix Imputation for Distributed Edge Clouds

  2024cites this paper
• Matrix Factorization Techniques in Machine Learning, Signal Processing, and Statistics

  2023cites this paper
• Item Graph Convolution Collaborative Filtering for Inductive Recommendations

  2023cites this paper
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution

  2023cites this paper
• Tensor completion with noisy side information

  2023cites this paper
• GInRec: A Gated Architecture for Inductive Recommendation using Knowledge Graphs

  2023cites this paper
• Inference for Low-rank Models without Estimating the Rank

  2023cites this paper
• Private Matrix Factorization with Public Item Features

  2023cites this paper
• Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networks

  2023cites this paper
• Variational Bayesian Inference for CP Tensor Completion with Subspace Information

  2022cites this paper
• Supplementary Material for “Fine-grained Generalisation Analysis of Inductive Matrix Completion”

  2022cites this paper
• PerFedSI: A Framework for Personalized Federated Learning with Side Information

  2022cites this paper
• Identifying circRNA-miRNA interaction based on multi-biological interaction fusion

  2022cites this paper
• Generalization Bounds for Inductive Matrix Completion in Low-noise Settings

  2022cites this paper
• From Bilinear Regression to Inductive Matrix Completion: A Quasi-Bayesian Analysis

  2022cites this paper
• Simple and Powerful Architecture for Inductive Recommendation Using Knowledge Graph Convolutions

  2022cites this paper
• Updated review of advances in microRNAs and complex diseases: taxonomy, trends and challenges of computational models

  2022cites this paper
• NRBdMF: A recommendation algorithm for predicting drug effects considering directionality

  2022cites this paper
• Feature and Nuclear Norm Minimization for Matrix Completion

  2022cites this paper
• Communicative Subgraph Representation Learning for Multi-Relational Inductive Drug-Gene Interaction Prediction

  2022cites this paper
• Near-Optimal Weighted Matrix Completion

  2022influential citation
• An interpretable bi-branch neural network for matrix completion

  2022cites this paper
• Geometric Inductive Matrix Completion: A Hyperbolic Approach with Unified Message Passing

  2022cites this paper
• Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm

  2022influential citation
• LRSVRG-IMC: An SVRG-Based Algorithm for LowRank Inductive Matrix Completion

  2022cites this paper
• Learning Personalized Product Recommendations with Customer Disengagement

  2021cites this paper
• Statistically and Computationally Efficient Linear Meta-representation Learning

  2021cites this paper
• Multi-weight Matrix Completion with Arbitrary Subspace Prior Information

  2021cites this paper
• Nonparametric Matrix Estimation with One-Sided Covariates

  2021cites this paper
• Tensor Estimation with Nearly Linear Samples Given Weak Side Information

  2021cites this paper
• University of Birmingham Fine-grained generalization analysis of inductive matrix completion

  2021cites this paper
• Tensor train completion: Local recovery guarantees via Riemannian optimization

  2021cites this paper
• Inductive Matrix Completion Using Graph Autoencoder

  2021cites this paper
• GNMR: A provable one-line algorithm for low rank matrix recovery

  2021cites this paper
• Sample Efficient Linear Meta-Learning by Alternating Minimization

  2021cites this paper
• Fast quantum state reconstruction via accelerated non-convex programming

  2021cites this paper
• An Inductive Logistic Matrix Factorization Model for Predicting Drug-Metabolite Association With Vicus Regularization

  2021cites this paper
• Progresses and challenges in link prediction

  2021cites this paper
• Policy Augmentation: An Exploration Strategy For Faster Convergence of Deep Reinforcement Learning Algorithms

  2021cites this paper
• Generating Artificial Core Users for Interpretable Condensed Data

  2021cites this paper
• Prediction of RNA-binding protein and alternative splicing event associations during epithelial-mesenchymal transition based on inductive matrix completion

  2021cites this paper
• Deep Collaborative Filtering for Prediction of Disease Genes

  2020cites this paper
• Prediction of circRNA-disease associations based on inductive matrix completion

  2020cites this paper
• Target identi fi cation among known drugs by deep learning from heterogeneous networks †

  2020cites this paper
• Locally Balanced Inductive Matrix Completion for Demand-Supply Inference in Stationless Bike-Sharing Systems

  2020cites this paper
• Riemannian gradient descent methods for graph-regularized matrix completion

  2020cites this paper
• Matrix Completion with Prior Subspace Information via Maximizing Correlation

  2020cites this paper
• Rich-Item Recommendations for Rich-Users via GCNN: Exploiting Dynamic and Static Side Information

  2020cites this paper
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees

  2020cites this paper
• Nonconvex Matrix Completion with Linearly Parameterized Factors

  2020influential citation
• Orthogonal Inductive Matrix Completion

  2020cites this paper
• Multi-Weight Nuclear Norm Minimization for Low-Rank Matrix Recovery in Presence of Subspace Prior Information

  2020cites this paper
• Note: low-rank tensor train completion with side information based on Riemannian optimization

  2020cites this paper
• Drug repositioning based on the target microRNAs using bilateral-inductive matrix completion

  2020cites this paper
• A Network-Based Embedding Method for Drug-Target Interaction Prediction

  2020cites this paper
• Projected Robust PCA with Application to Smooth Image Recovery

  2020cites this paper
• selfRL: Two-Level Self-Supervised Transformer Representation Learning for Link Prediction of Heterogeneous Biomedical Networks

  2020cites this paper
• Ensembling graph attention networks for human microbe-drug association prediction

  2020cites this paper
• Fast Exact Matrix Completion: A Unified Optimization Framework

  2020cites this paper
• Towards Open-World Recommendation: An Inductive Model-based Collaborative Filtering Approach

  2020cites this paper
• Tensor Completion with Nearly Linear Samples Given Weak Side Information

  2020cites this paper
• Network Representation Learning-Based Drug Mechanism Discovery and Anti-Inflammatory Response Against COVID-19

  2020cites this paper
• Single-cell RNAseq Imputation Based on Matrix Completion with Side Information

  2019cites this paper
• Collaborative Self-Attention for Recommender Systems

  2019influential citation
• Generalization Error Bounds for Kernel Matrix Completion and Extrapolation

  2019cites this paper
• A Novel Drug Repositioning Approach Based on Collaborative Metric Learning

  2019cites this paper
• A Greedy Algorithm for Matrix Recovery with Subspace Prior Information

  2019cites this paper
• Improved Inductive Matrix Completion Method for Predicting MicroRNA-Disease Associations

  2019cites this paper
• mHMDA: Human Microbe-Disease Association Prediction by Matrix Completion and Multi-Source Information

  2019cites this paper
• Drug repositioning via matrix completion with multi‐view side information

  2019cites this paper
• Provable Non-linear Inductive Matrix Completion

  2019influential citation
• Inductive Matrix Completion Based on Graph Neural Networks

  2019influential citation
• Fast Exact Matrix Completion: A Unifying Optimization Framework

  2019cites this paper
• Machine learning for problems with missing and uncertain data with applications to personalized medicine

  2019cites this paper
• MV-GCN: Multi-View Graph Convolutional Networks for Link Prediction

  2019cites this paper
• Tri-party deep network representation learning using inductive matrix completion

  2019cites this paper
• Deep Inductive Matrix Completion for Biomedical Interaction Prediction

  2019influential citation
• Collaborative Ranking Tags and Items via Cross-domain Recommendation

  2019cites this paper
• Graph Deep Learning: Methods and Applications

  2019cites this paper
• Learning Preferences with Side Information

  2019cites this paper
• Robust Inductive Matrix Completion Strategy to Explore Associations Between LincRNAs and Human Disease Phenotypes

  2019cites this paper
• Enhancing the Robustness of Neural Collaborative Filtering Systems Under Malicious Attacks

  2019cites this paper
• Function Prediction for G Protein-Coupled Receptors through Text Mining and Induction Matrix Completion

  2019cites this paper
• Inductive Graph Pattern Learning for Recommender Systems Based on a Graph Neural Network

  2019cites this paper