Matrix completion

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.

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.

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.

For example, in the low-rank matrix completion problem one may apply the regularization penalty taking the form of a nuclear norm

(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

In real world application, one often observe only a few entries corrupted at least by a small amount of noise.

Candès and Plan [9] 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.

Eriksson, Balzano and Nowak [10] showed that under mild assumptions each column of

One approach, proposed by Candès and Recht, is to form a convex relaxation of the problem and minimize the nuclear norm

The convex relaxation can be solved using semidefinite programming (SDP) by noticing that the optimization problem is equivalent to

State of the art solvers like SDPT3 can only handle matrices of size up to 100 by 100 [13] An alternative first order method that approximately solves the convex relaxation is the Singular Value Thresholding Algorithm introduced by Cai, Candès and Shen.

[13] 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

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

Another convex relaxation approach [14] is to minimize the Frobenius squared norm under a rank constraint.

Moreover, it can be converted into a feasible solution with a (slightly) larger objective by rounding the eigenvalues of Y greedily.

This approach is a special case of a more general reformulation technique, which can be applied to obtain a valid lower bound on any low-rank problem with a trace-matrix-convex objective.

(as measured by the root mean square error (RMSE)) with high probability.

Finally, although trimming may seem counter intuitive as it involves throwing out information, it ensures projecting

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data.

In the alternating minimization approach, the low-rank target matrix is written in a bilinear form:

The alternating minimization algorithm can be viewed as an approximate way to solve the following non-convex problem:

The AltMinComplete Algorithm proposed by Jain, Netrapalli and Sanghavi is listed here:[12] They showed that by observing

[citation needed] Several applications of matrix completion are summarized by Candès and Plan[9] as follows: 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.

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.

When we are not able to measure the complete network, which can be due to reasons such as private nodes, limited storage or compute resources, we only have a fraction of distance entries known.