Timezone: »

A Sparse Interactive Model for Matrix Completion with Side Information
Jin Lu · Guannan Liang · Jiangwen Sun · Jinbo Bi

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #91 #None
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.

Author Information

Jin Lu (University of Connecticut)
Guannan Liang (University of Connecticut)
Jiangwen Sun (University of Connecticut)
Jinbo Bi (University of Connecticut)

More from the Same Authors