A Sparse Interactive Model for Matrix Completion with Side Information
Matrix completion methods can benefit from side information besides the partially observed matrix. The use of side features describing the row and column entities of a matrix has been shown to reduce the sample complexity for completing the matrix. We propose a novel sparse formulation that explicitly models the interaction between the row and column side features to approximate the matrix entries. Unlike early methods, this model does not require the low-rank condition on the model parameter matrix. We prove that when the side features can span the latent feature space of the matrix to be recovered, the number of observed entries needed for an exact recovery is $O(\log N)$ where $N$ is the size of the matrix. When the side features are corrupted latent features of the matrix with a small perturbation, our method can achieve an $\epsilon$-recovery with $O(\log N)$ sample complexity, and maintains a $\O(N^{3/2})$ rate similar to classfic methods with no side information. An efficient linearized Lagrangian algorithm is developed with a strong guarantee of convergence. Empirical results show that our approach outperforms three state-of-the-art methods both in simulations and on real world datasets.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Cluster Developing 1-Bit Matrix Completion
Matrix completion has a long-time history of usage as the core technique of recommender systems. In particular, 1-bit matrix completion, which considers the prediction as a ``Recommended'' or ``Not Recommended'' question…
ClusteringMatrix CompletionRecommendation SystemsSparse Group Inductive Matrix Completion
We consider the problem of matrix completion with side information (\textit{inductive matrix completion}). In real-world applications many side-channel features are typically non-informative making feature selection an i…
feature selectionLow-Rank Matrix CompletionMatrix CompletionMatrix Completion with Sparse Noisy Rows
Exact matrix completion and low rank matrix estimation problems has been studied in different underlying conditions. In this work we study exact low-rank completion under non-degenerate noise model. Non-degenerate random…
Matrix CompletionApproximate Method of Variational Bayesian Matrix Factorization/Completion with Sparse Prior
We derive analytical expression of matrix factorization/completion solution by variational Bayes method, under the assumption that observed matrix is originally the product of low-rank dense and sparse matrices with addi…
Matrix CompletionLow Rank Quaternion Matrix Completion Based on Quaternion QR Decomposition and Sparse Regularizer
Matrix completion is one of the most challenging problems in computer vision. Recently, quaternion representations of color images have achieved competitive performance in many fields. Because it treats the color image a…
Matrix Completion