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 formula_1 represents the rating of movie formula_2 by customer formula_3, if customer formula_3 has watched movie formula_2 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 formula_6 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 formula_7
Low rank matrix completion.
One of the variants of the matrix completion problem is to find the lowest rank matrix formula_8 which matches the matrix formula_9, which we wish to recover, for all entries in the set formula_10 of observed entries. The mathematical formulation of this problem is as follows:
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 formula_9 to be recovered is known to be of rank formula_6, is to solve for formula_8 where formula_15
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.
Uniform sampling of observed entries.
To make the analysis tractable, it is often assumed that the set formula_10 of observed entries and fixed cardinality is sampled uniformly at random from the collection of all subsets of entries of cardinality formula_17. To further simplify the analysis, it is instead assumed that formula_10 is constructed by Bernoulli sampling, i.e. that each entry is observed with probability formula_19. If formula_20 is set to formula_21 where formula_22 is the desired expected cardinality of formula_10, and formula_24 are the dimensions of the matrix (let formula_25 without loss of generality), formula_17 is within formula_27 of formula_22 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.
Lower bound on number of observed entries.
Suppose the formula_29 by formula_30 matrix formula_9 (with formula_25) we are trying to recover has rank formula_6. There is an information theoretic lower bound on how many entries must be observed before formula_9 can be uniquely reconstructed. The set of formula_29 by formula_30 matrices with rank less than or equal to formula_6 is an algebraic variety in formula_38with dimension formula_39.
Using this result,
one can show that at least
formula_40
entries must be observed for matrix completion in
formula_41
to have a unique solution 
when
formula_42
Secondly, there must be at least one observed entry per row and column of formula_9. The Singular Value Decomposition of formula_9 is given by formula_45. If row formula_3 is unobserved, it is easy to see the formula_47 right singular vector of formula_9, formula_49, can be changed to some arbitrary value and still yield a matrix matching formula_9 over the set of observed entries. Similarly, if column formula_2 is unobserved, the formula_52 left singular vector of formula_9, formula_54 can be arbitrary. If we assume Bernoulli sampling of the set of observed entries, the Coupon collector effect implies that entries on the order of formula_55 must be observed to ensure that there is an observation from each row and column with high probability.
Combining the necessary conditions and assuming that formula_56 (a valid assumption for many practical applications), the lower bound on the number of observed entries required to prevent the problem of matrix completion from being underdetermined is on the order of formula_57.
Incoherence.
The concept of incoherence arose in compressed sensing. It is introduced in the context of matrix completion to ensure the singular vectors of formula_9 are not too "sparse" in the sense that all coordinates of each singular vector are of comparable magnitude instead of just a few coordinates having significantly larger magnitudes. The standard basis vectors are then undesirable as singular vectors, and the vector formula_59 in formula_60 is desirable. As an example of what could go wrong if the singular vectors are sufficiently "sparse", consider the formula_29 by formula_30 matrix formula_63 with singular value decomposition formula_64. Almost all the entries of formula_9 must be sampled before it can be reconstructed.
Candès and Recht define the coherence of a matrix formula_66 with column space an formula_67dimensional subspace of formula_60 as formula_69, where formula_70 is the orthogonal projection onto formula_71. Incoherence then asserts that given the singular value decomposition formula_45 of the formula_29 by formula_30 matrix formula_9,
for some formula_79.
Low rank matrix completion with noise.
In real world application, one often observe only a few entries corrupted at least by a small amount of noise. For example, in the Netflix problem, the ratings are uncertain. Candès and Plan showed that it is possible to fill in the many missing entries of large low-rank matrices from just a few noisy samples by nuclear norm minimization. The noisy model assumes that we observe
formula_80
where formula_81 is a noise term. Note that the noise can be either stochastic or deterministic. Alternatively the model can be expressed as
formula_82
where formula_83 is an formula_84 matrix with entries formula_85 for formula_86 assuming that formula_87 for some formula_88 .To recover the incomplete matrix, we try to solve the following optimization problem:
formula_89
Among all matrices consistent with the data, find the one with minimum nuclear norm. Candès and Plan have shown that this reconstruction is accurate. They have proved that when perfect noiseless recovery occurs, then matrix completion is stable vis a vis perturbations. The error is proportional to the noise level formula_90. Therefore, when the noise level is small, the error is small. Here the matrix completion problem does not obey the restricted isometry property (RIP). For matrices, the RIP would assume that the sampling operator obeys
formula_91
for all matrices formula_8 with sufficiently small rank and formula_93 sufficiently small.
The methods are also applicable to sparse signal recovery problems in which the RIP does not hold.
High rank matrix completion.
The high rank matrix completion in general is NP-Hard. However, with certain assumptions, some incomplete high rank matrix or even full rank matrix can be completed.
Eriksson, Balzano and Nowak have considered the problem of completing a matrix with the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. Since the columns belong to a union of subspaces, the problem may be viewed as a missing-data version of the subspace clustering problem. Let formula_8 be an formula_95 matrix whose (complete) columns lie in a union of at most formula_96 subspaces, each of formula_97, and assume formula_98. Eriksson, Balzano and Nowak showed that under mild assumptions each column of formula_8 can be perfectly recovered with high probability from an incomplete version so long as at least formula_100 entries of formula_8 are observed uniformly at random, with formula_102 a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces.
The algorithm involves several steps: (1) local neighborhoods; (2) local subspaces; (3) subspace refinement; (4) full matrix completion. This method can be applied to Internet distance matrix completion and topology identification.
Algorithms.
Various matrix completion algorithms have been proposed. These includes convex relaxation-based algorithm, gradient-based algorithm, and alternating minimization-based algorithm.
Convex relaxation.
The rank minimization problem is NP-hard. One approach, proposed by Candès and Recht, is to form a convex relaxation of the problem and minimize the nuclear norm formula_103 (which gives the sum of the singular values of formula_9) instead of formula_105 (which counts the number of non zero singular values of formula_9). This is analogous to minimizing the L1-norm rather than the L0-norm for vectors. The convex relaxation can be solved using semidefinite programming (SDP) by noticing that the optimization problem is equivalent to
formula_107
The complexity of using SDP to solve the convex relaxation is formula_108. State of the art solvers like SDP3 can only handle matrices of size up to 100 by 100 An alternative first order method that approximately solves the convex relaxation is the Singular Value Thresholding Algorithm introduced by Cai, Candès and Shen.
Candès and Recht show, using the study of random variables on Banach spaces, that if the number of observed entries is on the order of formula_109 (assume without loss of generality formula_25), the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability formula_111 for some constant formula_112. If the rank of formula_9 is small (formula_114), the size of the set of observations reduces to the order of formula_115. These results are near optimal, since the minimum number of entries that must be observed for the matrix completion problem to not be underdetermined is on the order of formula_116.
This result has been improved by Candès and Tao. They achieve bounds that differ from the optimal bounds only by polylogarithmic factors by strengthening the assumptions. Instead of the incoherence property, they assume the strong incoherence property with parameter formula_117. This property states that:
Intuitively, strong incoherence of a matrix formula_66 asserts that the orthogonal projections of standard basis vectors to formula_66 has magnitudes that have high likelihood if the singular vectors were distributed randomly.
Candès and Tao find that when formula_6 is formula_127 and the number of observed entries is on the order of formula_128, the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability formula_111 for some constant formula_112. For arbitrary formula_6, the number of observed entries sufficient for this assertion hold true is on the order of formula_132
Gradient descent.
Keshavan, Montanari and Oh consider a variant of matrix completion where the rank of the formula_29 by formula_30 matrix formula_9, which is to be recovered, is known to be formula_6. They assume Bernoulli sampling of entries, constant aspect ratio formula_137, bounded magnitude of entries of formula_9 (let the upper bound be formula_139), and constant condition number formula_140 (where formula_141 and formula_142 are the largest and smallest singular values of formula_9 respectively). Further, they assume the two incoherence conditions are satisfied with formula_144 and formula_145 where formula_144 and formula_147 are constants. Let formula_148 be a matrix that matches formula_9 on the set formula_10 of observed entries and is 0 elsewhere. They then propose the following algorithm:
Steps 1 and 2 of the algorithm yield a matrix formula_156 very close to the true matrix formula_9 (as measured by the root mean square error (RMSE) with high probability. In particular, with probability formula_169, formula_170 for some constant formula_171. formula_172 denotes the Frobenius norm. Note that the full suite of assumptions is not needed for this result to hold. The incoherence condition, for example, only comes into play in exact reconstruction. Finally, although trimming may seem counter intuitive as it involves throwing out information, it ensures projecting formula_148 onto its first formula_6 principal components gives more information about the underlying matrix formula_9 than about the observed entries.
In Step 3, the space of candidate matrices formula_159 can be reduced by noticing that the inner minimization problem has the same solution for formula_177 as for formula_178 where formula_179 and formula_180 are orthonormal formula_6 by formula_6 matrices. Then gradient descent can be performed over the cross product of two Grassman manifolds. If formula_183 and the observed entry set is in the order of formula_184, the matrix returned by Step 3 is exactly formula_9. Then the algorithm is order optimal, since we know that for the matrix completion problem to not be underdetermined the number of entries must be in the order of formula_184.
Alternating least squares minimization.
Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix problem. In the alternating minimization approach, the low-rank target matrix is written in a bilinear form:
formula_187;
the algorithm then alternates between finding the best formula_66 and the best formula_189. While the overall problem is non-convex, each sub-problem is typically convex and can be solved efficiently. Jain, Netrapalli and Sanghavi have given one of the first guarantees for performance of alternating minimization for both matrix completion and matrix sensing.
The alternating minimization algorithm can be viewed as an approximate way to solve the following non-convex problem:
formula_190
The AltMinComplete Algorithm proposed by Jain, Netrapalli and Sanghavi is listed here:
They showed that by observing formula_208 random entries of an incoherent matrix formula_9, AltMinComplete algorithm can recover formula_9 in formula_211 steps. In terms of sample complexity (formula_212), theoretically, Alternating Minimization may require a bigger formula_191 than Convex Relaxation. However empirically it seems not the case which implies that the sample complexity bounds can be further tightened. In terms of time complexity, they showed that AltMinComplete needs time
formula_214.
It is worth noting that, although convex relaxation based methods have rigorous analysis, alternating minimization based algorithms are more successful in practice.
Applications.
Several applications of matrix completion are summarized by Candès and Plan as follows:
Collaborative filtering.
Collaborative filtering is the task of making automatic predictions about the interests of a user by collecting taste information from many users. Companies like Apple, Amazon, Barnes and Noble, and Netflix are trying to predict their user preferences from partial knowledge. In these kind of matrix completion problem, the unknown full matrix is often considered low rank because only a few factors typically contribute to an individual's tastes or preference.
System identification.
In control, one would like to fit a discrete-time linear time-invariant state-space model
formula_215
to a sequence of inputs formula_216 and outputs formula_217. The vector formula_218 is the state of the system at time formula_219 and formula_30 is the order of the system model. From the input/output pair, one would like to recover the matrices formula_221 and the initial state formula_222. This problem can also be viewed as a low-rank matrix completion problem.
Internet of things (IoT) localization.
The localization (or global positioning) problem emerges naturally in IoT sensor networks. The problem is to recover the sensor map in Euclidean space from a local or partial set of pairwise distances. Thus it is a matrix completion problem with rank two if the sensors are located in a 2-D plane and three if they are in a 3-D space.