Matrix completion

Matrix completion is the task of filling in the missing entries of a partially observed matrix. 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 term-document 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. Matrix completion is the task of filling in the missing entries of a partially observed matrix. 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 term-document 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 matrix completion often seeks 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 there are tractable 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|_{*}} 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 {egin{aligned}&{underset {X}{ ext{min}}}&{ ext{rank}}(X)\&{ ext{subject to}}&X_{ij}=M_{ij}&;;forall i,jin 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,jin E} 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. To make the analysis tractable, it is often assumed that the set E {displaystyle E} of observed entries and fixed cardinality is sampled uniformly at random from the collection of all subsets of entries of cardinality | E | {displaystyle |E|} . To further simplify the analysis, it is instead assumed that E {displaystyle E} is constructed by Bernoulli sampling, i.e. that each entry is observed with probability p {displaystyle p} . If p {displaystyle p} is set to N m n {displaystyle {frac {N}{mn}}} where N {displaystyle N} is the desired expected cardinality of E {displaystyle E} , and m , n {displaystyle m,;n} are the dimensions of the matrix (let m < n {displaystyle m<n} without loss of generality), | E | {displaystyle |E|} is within O ( n log ⁡ n ) {displaystyle O(nlog n)} of N {displaystyle N} with high probability, thus Bernoulli sampling is a good approximation for uniform sampling. Another simplification is to assume that entries are sampled independently and with replacement.