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 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 -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.
This paper addresses the problem of matrix completion when the side information about the features is available in form of features vector matrices X and Y. In such problems the matrix to be completed can be written as F = X^T G Y. The paper considers a model in which the matrix F is low rank and G is sparse. They propose a recovery method that minimizes the nuclear norm of X^T G Y and \ell_1 norm of G. This seems to be a fairly intuitive approach to complete the matrices that follow this model. The paper also proposes a solution along the lines of regularized maximum likelihood formulation for the matrix completion under Gaussian noise assumptions. Finally, the authors propose a LADMM algorithm for solving the problem and provide a proof of its convergence. Overall, the paper looks fairly exhaustive in the theoretical analysis of the proposed solution.
 The main comments are as follows:   1) The problem formulation under noise given in equation (2) of the paper seems to be problematic. It is not clear where the noise enters in the overall setup. Generally, the observations are corrupted by noise, i.e., R_{\Omega}(F) =  R_{\Omega} (X^T G Y + N). Under such a scenario, the likelihood assuming gaussian noise is given by || R_{\Omega}(F) -  R_{\Omega} (X^T G Y )  ||_F^2. The paper however does something confusing. It introduces a matrix E, and introduces a constraint  R_{\Omega}(E) = R_{\Omega}(F) and uses the likelihood term ||E - X^T G Y||_F^2.  This is problematic because the estimated low rank matrix E is constrained to have same value as the noisy observation. This basically will eliminate the possibility of de-noising the observed part of the matrix. As per my knowledge of existing literature for noisy matrix completion problem, the observed entries of the estimated matrix are never constrained to be equal to their noisy observations.    2) The main recovery result given in Theorem 2 introduces model assumptions ||E||_* <= \alpha and ||G||_1 <= \gamma. These assumptions raise some questions whose answers are not well argued in the paper. Firstly, even though bounds on any norm of the model parameters makes it inherently less complex, bounded nuclear norm and \ell_1 norm does not necessarily imply low rank E and sparse G. The whole paper is built upon the notion that G is sparse and E is low rank but the assumption in theorem does not necessary impose these on the model. In this regard looking at the Theorem statement it is not clear why authors minimize weighed sum nuclear norm and \ell_1 norm. Under the model assumptions stated in the Theorem a straight forward alternative is to consider constrained maximum likelihood formulation, i.e., put the constraints ||E||_* <= \alpha, ||G||_1 <= \gamma explicitly in the recovery problem formulation. A discussion based on these points will significantly improve the clarity of the paper from motivational point of view.     3) It is not clear how do the recovery results in the Theorem statement depend on the regularization parameters \lambda_E and \lambda_G.  As the value of regularization parameters increases the error should increase for very large values of these parameters. But this is not evident from the recovery bounds.    4) In the final LADMM formulation it is not clear why authors introduce an auxiliary variable C. Even without C, the G update step and E update are similar. For clarity authors need to explain why C is needed.   Minor Comments:  1) In abstract, it is not clear what is the size of the matrix. Mentioning that it is N = max{n_1, n_2} where n_1 is the number of rows and n_2 is number of columns.  2) Typo ’impaire’ on line 125.  3) In statement of Theorem 2, \Chi^2 is not defined.  4) After Theorem 3, a comment on how to calculate \tau_a and \tau_b would help the reader to use the proposed algorithm.