[Full Text], [Code]
In many practical problems of interest, one would like to estimate a matrix from a sampling of its entries. The matrix we wish to estimate is known to be structured in the sense that it is low-rank or approximately low-rank. Given below is a practical scenario where one would like to be able to recover a low-rank matrix from a sampling of its entries.
The Netflix problem - In the area of recommender systems, users submit ratings on a subset of entries in a database, and the vendor provides recommendations based on the user’s preferences. Because users only rate a few items, one would like to infer their preference for unrated items. A special instance of this problem is the now famous Netflix problem. Users (rows of the data matrix) are given the opportunity to rate movies (columns of the data matrix), but users typically rate only very few movies so that there are very few scattered observed entries of this data matrix. Yet one would like to complete this matrix so that the vendor (here Netix) might recommend titles that any particular user is likely to be willing to order. In this case, the data matrix of all user-ratings may be approximately low-rank because it is commonly believed that only a few factors contribute to an individual’s tastes or preferences.
In this project, I present an Alternating Direction Method of Multipliers (ADMM) algorithm that has been widely used for solving several convex and non-convex optimization problems by breaking them into smaller sub-problems. Further, I even went beyond and improved the results presented in the paper by imposing a sparsity constraint on the matrix in the DCT basis. This is a common condition for natural images, and I demonstrate a significant improvement in reconstruction results.
Given below are the reconstructions in the case of imposing the sparsity constraint and not imposing the sparsity constraint. As we can see, imposing the sparsity constraint significantly improves the reconstruction results.