Matrix Completion on Graphs - implementation -

Vassilis Kalofolias just sent me the following:

Dear Igor, 

I am a student of Pierre Vandergheynst at EPFL and we recently had our paper on "Matrix Completion on Graphs" accepted at NIPS workshop on robustness of high dimensional data.

We have published Matlab code for our algorithm here, I think it could fit nicely somewhere in your blog space :)

https://lts2research.epfl.ch/software/matrix-completion-on-graphs/

I am also attaching the tar file with the code.

Thanks!

best regards,
Vassilis Kalofolias
PhD candidate,
LTS2, EPFL

Matrix Completion on Graphs by Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, Pierre Vandergheynst

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Although the problem under the standard low rank assumption is NP-hard, Cand\`es and Recht showed that it can be exactly relaxed if the number of observed entries is sufficiently large. In this work, we introduce a novel matrix completion model that makes use of proximity information about rows and columns by assuming they form communities. This assumption makes sense in several real-world problems like in recommender systems, where there are communities of people sharing preferences, while products form clusters that receive similar ratings. Our main goal is thus to find a low-rank solution that is structured by the proximities of rows and columns encoded by graphs. We borrow ideas from manifold learning to constrain our solution to be smooth on these graphs, in order to implicitly force row and column proximities. Our matrix recovery model is formulated as a convex non-smooth optimization problem, for which a well-posed iterative scheme is provided. We study and evaluate the proposed matrix completion on synthetic and real data, showing that the proposed structured low-rank recovery model outperforms the standard matrix completion model in many situations. 

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.