Matrix completion is the task of filling in the missing entries of a partially observed matrix, which is equivalent to performing data imputation in statistics. A wide range of datasets are naturally organized in matrix form. One example is the movie-ratings matrix, as appears in the Netflix problem: Given a ratings matrix in which each entry ( i , j ) {\displaystyle (i,j)} represents the rating of movie j {\displaystyle j} by customer i {\displaystyle i} , if customer i {\displaystyle i} has watched movie j {\displaystyle j} and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. Another example is the document-term matrix: The frequencies of words used in a collection of documents can be represented as a matrix, where each entry corresponds to the number of times the associated term appears in the indicated document. Without any restrictions on the number of degrees of freedom in the completed matrix, this problem is underdetermined since the hidden entries could be assigned arbitrary values. Thus, we require some assumption on the matrix to create a well-posed problem, such as assuming it has maximal determinant, is positive definite, or is low-rank. For example, one may assume the matrix has low-rank structure, and then seek to find the lowest rank matrix or, if the rank of the completed matrix is known, a matrix of rank r {\displaystyle r} that matches the known entries. The illustration shows that a partially revealed rank-1 matrix (on the left) can be completed with zero-error (on the right) since all the rows with missing entries should be the same as the third row. In the case of the Netflix problem the ratings matrix is expected to be low-rank since user preferences can often be described by a few factors, such as the movie genre and time of release. Other applications include computer vision, where missing pixels in images need to be reconstructed, detecting the global positioning of sensors in a network from partial distance information, and multiclass learning. The matrix completion problem is in general NP-hard, but under additional assumptions there are efficient algorithms that achieve exact reconstruction with high probability. In statistical learning point of view, the matrix completion problem is an application of matrix regularization which is a generalization of vector regularization. For example, in the low-rank matrix completion problem one may apply the regularization penalty taking the form of a nuclear norm R ( X ) = λ ‖ X ‖ ∗ {\displaystyle R(X)=\lambda \|X\|_{*}}
Low rank matrix completion One of the variants of the matrix completion problem is to find the lowest rank matrix X {\displaystyle X} which matches the matrix M {\displaystyle M} , which we wish to recover, for all entries in the set E {\displaystyle E} of observed entries. The mathematical formulation of this problem is as follows:
min X rank ( X ) subject to X i j = M i j ∀ i , j ∈ E {\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}
Candès and Recht proved that with assumptions on the sampling of the observed entries and sufficiently many sampled entries this problem has a unique solution with high probability. An equivalent formulation, given that the matrix M {\displaystyle M} to be recovered is known to be of rank r {\displaystyle r} , is to solve for X {\displaystyle X} where X i j = M i j ∀ i , j ∈ E {\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}
Assumptions A number of assumptions on the sampling of the observed entries and the number of sampled entries are frequently made to simplify the analysis and to ensure the problem is not underdetermined.
… excerpt ends here. Continue reading the full article.
