Name
Abstract | ||
|---|---|---|
Matrix completion methods can benefit from side information besides the partially observed matrix. The use of side features that describe 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 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. If 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. If side information is useless, our method maintains a O(N-3/2) sampling rate similar to classic methods. An efficient linearized Lagrangian algorithm is developed with a convergence guarantee. Empirical results show that our approach outperforms three state-of-the-art methods both in simulations and on real world datasets. |
Year | Venue | Field |
|---|---|---|
2016 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016) | Combinatorics,Mathematical optimization,Square matrix,Permutation matrix,Augmented matrix,State-transition matrix,Gaussian elimination,Band matrix,Block matrix,Mathematics,Sparse matrix |
DocType | Volume | ISSN |
Conference | 29 | 1049-5258 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jin Lu | 1 | 32 | 4.46 |
| Liang, Guannan | 2 | 0 | 2.70 |
| Jiangwen Sun | 3 | 66 | 8.73 |
| Jinbo Bi | 4 | 1432 | 104.24 |