The best example of matrix completion in real life is perhaps the ``Netflix problem'', where different customers have rated some of the movies, but no customer has rated all the movies, and at the same time no movie has been rated by all the customers. If we arrange all the customer ratings as a matrix, where each known entry Aij is the rating given by customer i of movie j, then there are many missing rating values in the matrix. Matrix completion here means: try to fill the missing rating values, that is, to deduce what rating a customer will give to an un-watched movie.
Mathematically, one of the widely used strategies for matrix completion, for an input matrix A of size m x n with unknown entries, is to compute two new matrices W and H, where matrix W is of size m x k and matrix H is of size n x k. Here, k is called the dimension of the latent space in machine learning. The goal is that a multiplication of matrix W with matrix HT (transpose of matrix H) gives an approximation of matrix A, see the above figure.
A commonly used numerical strategy for computing matrices W and H is the so-called stochastic gradient decent (SGD) method, for which the details and implementation can be found in [2]. Moreover, the authors of [2] have developed a parallel code, named NOMAD, that can run the SGD method on a parallel computer.
In this project, the candidate is expected to improve NOMAD in two aspects: (1) a better division of work that can lead to a higher ratio of computation versus data communication (the higher the better for the computing speed); (2) an improved parallel implementation that avoids blindly passing data to a random processor that may not be able to contribute (thus an unnecessary waste of time). More technical details of the project can be found in this document.
Needed background of the student:
- Good programming skills (knowledge about parallel programming will be a plus);
- Basic knowledge about numerical algorithms;
- Courage of tackling challenging problems in the intersection of scientific computing and machine learning.
Expected outcome:
- Programming skills that are suitable for using large parallel computers;
- Improved knowledge in scientific computing and machine learning;
- Hands-on experience of using modern computer architectures.
References:
[1] Wikipedia: https://en.wikipedia.org/wiki/Matrix_completion
[2] Hyokun Yun, Hsiang-Fu Yu, Cho-Jui Hsieh, S. V. N. Vishwanathan, Inderjit Dhillon. NOMAD: Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion. Proceedings of the VLDB Endowment. 2014.
[3] Chen, Z., Wang, S. A review on matrix completion for recommender systems. Knowl Inf Syst 64, 1–34 (2022).