Matrix completion

Last updated
Matrix completion of a partially revealed 5 by 5 matrix with rank-1. Left: observed incomplete matrix; Right: matrix completion result. Rank-1-matrix-completion.png
Matrix completion of a partially revealed 5 by 5 matrix with rank-1. Left: observed incomplete matrix; Right: matrix completion result.

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 represents the rating of movie by customer , if customer has watched movie 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.

Contents

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. [1] [2]

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 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

Low rank matrix completion

One of the variants of the matrix completion problem is to find the lowest rank matrix which matches the matrix , which we wish to recover, for all entries in the set of observed entries. The mathematical formulation of this problem is as follows:

Candès and Recht [3] 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 to be recovered is known to be of rank , is to solve for where

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 of observed entries and fixed cardinality is sampled uniformly at random from the collection of all subsets of entries of cardinality . To further simplify the analysis, it is instead assumed that is constructed by Bernoulli sampling, i.e. that each entry is observed with probability . If is set to where is the desired expected cardinality of , and are the dimensions of the matrix (let without loss of generality), is within of with high probability, thus Bernoulli sampling is a good approximation for uniform sampling. [3] Another simplification is to assume that entries are sampled independently and with replacement. [4]

Lower bound on number of observed entries

Suppose the by matrix (with ) we are trying to recover has rank . There is an information theoretic lower bound on how many entries must be observed before can be uniquely reconstructed. The set of by matrices with rank less than or equal to is an algebraic variety in with dimension . Using this result, one can show that at least entries must be observed for matrix completion in to have a unique solution when . [5]

Secondly, there must be at least one observed entry per row and column of . The singular value decomposition of is given by . If row is unobserved, it is easy to see the right singular vector of , , can be changed to some arbitrary value and still yield a matrix matching over the set of observed entries. Similarly, if column is unobserved, the left singular vector of , 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 must be observed to ensure that there is an observation from each row and column with high probability. [6]

Combining the necessary conditions and assuming that (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 .

Incoherence

The concept of incoherence arose in compressed sensing. It is introduced in the context of matrix completion to ensure the singular vectors of 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. [7] [8] The standard basis vectors are then undesirable as singular vectors, and the vector in is desirable. As an example of what could go wrong if the singular vectors are sufficiently "sparse", consider the by matrix with singular value decomposition . Almost all the entries of must be sampled before it can be reconstructed.

Candès and Recht [3] define the coherence of a matrix with column space an dimensional subspace of as , where is the orthogonal projection onto . Incoherence then asserts that given the singular value decomposition of the by matrix ,

  1. The entries of have magnitudes upper bounded by

for some .

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 [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. The noisy model assumes that we observe

where is a noise term. Note that the noise can be either stochastic or deterministic. Alternatively the model can be expressed as

where is an matrix with entries for assuming that for some .To recover the incomplete matrix, we try to solve the following optimization problem:

Among all matrices consistent with the data, find the one with minimum nuclear norm. Candès and Plan [9] 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 . 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

for all matrices with sufficiently small rank and 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 [10] 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 be an matrix whose (complete) columns lie in a union of at most subspaces, each of , and assume . Eriksson, Balzano and Nowak [10] showed that under mild assumptions each column of can be perfectly recovered with high probability from an incomplete version so long as at least entries of are observed uniformly at random, with 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 for Low-Rank Matrix Completion

Various matrix completion algorithms have been proposed. [8] These includes convex relaxation-based algorithm, [3] gradient-based algorithm, [11] and alternating minimization-based algorithm. [12]

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 (which gives the sum of the singular values of ) instead of (which counts the number of non zero singular values of ). [3] 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

The complexity of using SDP to solve the convex relaxation is . 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 (assume without loss of generality ), the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability for some constant . If the rank of is small (), the size of the set of observations reduces to 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 .

This result has been improved by Candès and Tao. [6] 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 . This property states that:

  1. for and for
  2. The entries of are bounded in magnitude by

Intuitively, strong incoherence of a matrix asserts that the orthogonal projections of standard basis vectors to has magnitudes that have high likelihood if the singular vectors were distributed randomly. [7]

Candès and Tao find that when is and the number of observed entries is on the order of , the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability for some constant . For arbitrary , the number of observed entries sufficient for this assertion hold true is on the order of

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

By introducing an orthogonal projection matrix (meaning ) to model the rank of via and taking this problem's convex relaxation, we obtain the following semidefinite program

If Y is a projection matrix (i.e., has binary eigenvalues) in this relaxation, then the relaxation is tight. Otherwise, it gives a valid lower bound on the overall objective. Moreover, it can be converted into a feasible solution with a (slightly) larger objective by rounding the eigenvalues of Y greedily. [14] Remarkably, this convex relaxation can be solved by alternating minimization on X and Y without solving any SDPs, and thus it scales beyond the typical numerical limits of state-of-the-art SDP solvers like SDPT3 or Mosek.

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. [15]


Gradient descent

Keshavan, Montanari and Oh [11] consider a variant of matrix completion where the rank of the by matrix , which is to be recovered, is known to be . They assume Bernoulli sampling of entries, constant aspect ratio , bounded magnitude of entries of (let the upper bound be ), and constant condition number (where and are the largest and smallest singular values of respectively). Further, they assume the two incoherence conditions are satisfied with and where and are constants. Let be a matrix that matches on the set of observed entries and is 0 elsewhere. They then propose the following algorithm:

  1. Trim by removing all observations from columns with degree larger than by setting the entries in the columns to 0. Similarly remove all observations from rows with degree larger than .
  2. Project onto its first principal components. Call the resulting matrix .
  3. Solve where is some regularization function by gradient descent with line search. Initialize at where . Set as some function forcing to remain incoherent throughout gradient descent if and are incoherent.
  4. Return the matrix .

Steps 1 and 2 of the algorithm yield a matrix very close to the true matrix (as measured by the root mean square error (RMSE)) with high probability. In particular, with probability , for some constant . 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 onto its first principal components gives more information about the underlying matrix than about the observed entries.

In Step 3, the space of candidate matrices can be reduced by noticing that the inner minimization problem has the same solution for as for where and are orthonormal by matrices. Then gradient descent can be performed over the cross product of two Grassman manifolds. If and the observed entry set is in the order of , the matrix returned by Step 3 is exactly . 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 .

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:

;

the algorithm then alternates between finding the best and the best . While the overall problem is non-convex, each sub-problem is typically convex and can be solved efficiently. Jain, Netrapalli and Sanghavi [12] 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:

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

  1. Input: observed set , values
  2. Partition into subsets with each element of belonging to one of the with equal probability (sampling with replacement)
  3. i.e., top- left singular vectors of
  4. Clipping: Set all elements of that have magnitude greater than to zero and orthonormalize the columns of
  5. fordo
  6. end for
  7. Return

They showed that by observing random entries of an incoherent matrix , AltMinComplete algorithm can recover in steps. In terms of sample complexity (), theoretically, Alternating Minimization may require a bigger 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

.

It is worth noting that, although convex relaxation based methods have rigorous analysis, alternating minimization based algorithms are more successful in practice.[ citation needed ]

Applications

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

to a sequence of inputs and outputs . The vector is the state of the system at time and is the order of the system model. From the input/output pair, one would like to recover the matrices and the initial state . 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. [16]

Social Networks Recovery

Most of the real-world social networks have low-rank distance matrices. 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. Criminal networks are a good example of such networks. Low-rank Matrix Completion can be used to recover these unobserved distances. [17]

See also

Related Research Articles

In particle physics, the Dirac equation is a relativistic wave equation derived by British physicist Paul Dirac in 1928. In its free form, or including electromagnetic interactions, it describes all spin-12 massive particles, called "Dirac particles", such as electrons and quarks for which parity is a symmetry. It is consistent with both the principles of quantum mechanics and the theory of special relativity, and was the first theory to account fully for special relativity in the context of quantum mechanics. It was validated by accounting for the fine structure of the hydrogen spectrum in a completely rigorous way.

<span class="mw-page-title-main">Four-vector</span> 4-dimensional vector in relativity

In special relativity, a four-vector is an object with four components, which transform in a specific way under Lorentz transformations. Specifically, a four-vector is an element of a four-dimensional vector space considered as a representation space of the standard representation of the Lorentz group, the representation. It differs from a Euclidean vector in how its magnitude is determined. The transformations that preserve this magnitude are the Lorentz transformations, which include spatial rotations and boosts.

<span class="mw-page-title-main">Jensen's inequality</span> Theorem of convex functions

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906, building on an earlier proof of the same inequality for doubly-differentiable functions by Otto Hölder in 1889. Given its generality, the inequality appears in many forms depending on the context, some of which are presented below. In its simplest form the inequality states that the convex transformation of a mean is less than or equal to the mean applied after convex transformation; it is a simple corollary that the opposite is true of concave transformations.

Linear elasticity is a mathematical model of how solid objects deform and become internally stressed due to prescribed loading conditions. It is a simplification of the more general nonlinear theory of elasticity and a branch of continuum mechanics.

In mathematics, the Hodge star operator or Hodge star is a linear map defined on the exterior algebra of a finite-dimensional oriented vector space endowed with a nondegenerate symmetric bilinear form. Applying the operator to an element of the algebra produces the Hodge dual of the element. This map was introduced by W. V. D. Hodge.

In mathematics, an almost complex manifold is a smooth manifold equipped with a smooth linear complex structure on each tangent space. Every complex manifold is an almost complex manifold, but there are almost complex manifolds that are not complex manifolds. Almost complex structures have important applications in symplectic geometry.

In physics, the Hamilton–Jacobi equation, named after William Rowan Hamilton and Carl Gustav Jacob Jacobi, is an alternative formulation of classical mechanics, equivalent to other formulations such as Newton's laws of motion, Lagrangian mechanics and Hamiltonian mechanics.

<span class="mw-page-title-main">Two-state quantum system</span> Simple quantum mechanical system

In quantum mechanics, a two-state system is a quantum system that can exist in any quantum superposition of two independent quantum states. The Hilbert space describing such a system is two-dimensional. Therefore, a complete basis spanning the space will consist of two independent states. Any two-state system can also be seen as a qubit.

In mathematics, a change of variables is a basic technique used to simplify problems in which the original variables are replaced with functions of other variables. The intent is that when expressed in new variables, the problem may become simpler, or equivalent to a better understood problem.

In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly converging iterative process.

The intent of this article is to highlight the important points of the derivation of the Navier–Stokes equations as well as its application and formulation for different families of fluids.

In mathematics, the spectral theory of ordinary differential equations is the part of spectral theory concerned with the determination of the spectrum and eigenfunction expansion associated with a linear ordinary differential equation. In his dissertation, Hermann Weyl generalized the classical Sturm–Liouville theory on a finite closed interval to second order differential operators with singularities at the endpoints of the interval, possibly semi-infinite or infinite. Unlike the classical case, the spectrum may no longer consist of just a countable set of eigenvalues, but may also contain a continuous part. In this case the eigenfunction expansion involves an integral over the continuous part with respect to a spectral measure, given by the Titchmarsh–Kodaira formula. The theory was put in its final simplified form for singular differential equations of even degree by Kodaira and others, using von Neumann's spectral theorem. It has had important applications in quantum mechanics, operator theory and harmonic analysis on semisimple Lie groups.

In continuum mechanics, a compatible deformation tensor field in a body is that unique tensor field that is obtained when the body is subjected to a continuous, single-valued, displacement field. Compatibility is the study of the conditions under which such a displacement field can be guaranteed. Compatibility conditions are particular cases of integrability conditions and were first derived for linear elasticity by Barré de Saint-Venant in 1864 and proved rigorously by Beltrami in 1886.

Least-squares support-vector machines (LS-SVM) for statistics and in statistical modeling, are least-squares versions of support-vector machines (SVM), which are a set of related supervised learning methods that analyze data and recognize patterns, and which are used for classification and regression analysis. In this version one finds the solution by solving a set of linear equations instead of a convex quadratic programming (QP) problem for classical SVMs. Least-squares SVM classifiers were proposed by Johan Suykens and Joos Vandewalle. LS-SVMs are a class of kernel-based learning methods.

In mathematics, the method of steepest descent or saddle-point method is an extension of Laplace's method for approximating an integral, where one deforms a contour integral in the complex plane to pass near a stationary point, in roughly the direction of steepest descent or stationary phase. The saddle-point approximation is used with integrals in the complex plane, whereas Laplace’s method is used with real integrals.

<span class="mw-page-title-main">Symmetry in quantum mechanics</span> Properties underlying modern physics

Symmetries in quantum mechanics describe features of spacetime and particles which are unchanged under some transformation, in the context of quantum mechanics, relativistic quantum mechanics and quantum field theory, and with applications in the mathematical formulation of the standard model and condensed matter physics. In general, symmetry in physics, invariance, and conservation laws, are fundamentally important constraints for formulating physical theories and models. In practice, they are powerful methods for solving problems and predicting what can happen. While conservation laws do not always give the answer to the problem directly, they form the correct constraints and the first steps to solving a multitude of problems.

In machine learning, the kernel embedding of distributions comprises a class of nonparametric methods in which a probability distribution is represented as an element of a reproducing kernel Hilbert space (RKHS). A generalization of the individual data-point feature mapping done in classical kernel methods, the embedding of distributions into infinite-dimensional feature spaces can preserve all of the statistical features of arbitrary distributions, while allowing one to compare and manipulate distributions using Hilbert space operations such as inner products, distances, projections, linear transformations, and spectral analysis. This learning framework is very general and can be applied to distributions over any space on which a sensible kernel function may be defined. For example, various kernels have been proposed for learning from data which are: vectors in , discrete classes/categories, strings, graphs/networks, images, time series, manifolds, dynamical systems, and other structured objects. The theory behind kernel embeddings of distributions has been primarily developed by Alex Smola, Le Song , Arthur Gretton, and Bernhard Schölkopf. A review of recent works on kernel embedding of distributions can be found in.

Menter's Shear Stress Transport turbulence model, or SST, is a widely used and robust two-equation eddy-viscosity turbulence model used in Computational Fluid Dynamics. The model combines the k-omega turbulence model and K-epsilon turbulence model such that the k-omega is used in the inner region of the boundary layer and switches to the k-epsilon in the free shear flow.

In number theory, the prime omega functions and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. That is, if we have a prime factorization of of the form for distinct primes , then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.

In optimal transport, a branch of mathematics, polar factorization of vector fields is a basic result due to Brenier (1987), with antecedents of Knott-Smith (1984) and Rachev (1985), that generalizes many existing results among which are the polar decomposition of real matrices, and the rearrangement of real-valued functions.

References

  1. Johnson, Charles R. (1990). "Matrix completion problems: A survey". Matrix Theory and Applications. Proceedings of Symposia in Applied Mathematics. Vol. 40. pp. 171–198. doi:10.1090/psapm/040/1059486. ISBN   9780821801543.
  2. Laurent, Monique (2008). "Matrix Completion Problems". Encyclopedia of Optimization. Vol. 3. pp. 221–229. doi:10.1007/978-0-387-74759-0_355. ISBN   978-0-387-74758-3.
  3. 1 2 3 4 5 Candès, E. J.; Recht, B. (2009). "Exact Matrix Completion via Convex Optimization". Foundations of Computational Mathematics . 9 (6): 717–772. arXiv: 0805.4471 . doi: 10.1007/s10208-009-9045-5 .
  4. Recht, B. (2009). "A Simpler Approach to Matrix Completion" (PDF). Journal of Machine Learning Research . 12: 3413–3430. arXiv: 0910.0651 . Bibcode:2009arXiv0910.0651R.
  5. Xu, Zhiqiang (2018). "The minimal measurement number for low-rank matrix recovery". Applied and Computational Harmonic Analysis . 44 (2): 497–508. arXiv: 1505.07204 . doi:10.1016/j.acha.2017.01.005. S2CID   11990443.
  6. 1 2 Candès, E. J.; Tao, T. (2010). "The Power of Convex Relaxation: Near-Optimal Matrix Completion". IEEE Transactions on Information Theory . 56 (5): 2053–2080. arXiv: 0903.1476 . doi:10.1109/TIT.2010.2044061. S2CID   1255437.
  7. 1 2 Tao, T. (10 March 2009). "The power of convex relaxation: near-optimal matrix completion". What's new.
  8. 1 2 Nguyen, L.T.; Kim, J.; Shim, B. (10 July 2019). "Low-Rank Matrix Completion: A Contemporary Survey". IEEE Access . 7 (1): 94215–94237. arXiv: 1907.11705 . Bibcode:2019arXiv190711705N. doi:10.1109/ACCESS.2019.2928130. S2CID   198930899.
  9. 1 2 3 Candès, E. J.; Plan, Y. (2010). "Matrix Completion with Noise". Proceedings of the IEEE . 98 (6): 925–936. arXiv: 0903.3131 . doi:10.1109/JPROC.2009.2035722. S2CID   109721.
  10. 1 2 Eriksson, B.; Balzano, L.; Nowak, R. (2011). "High-Rank Matrix Completion and Subspace Clustering with Missing Data". arXiv: 1112.5629 [cs.IT].
  11. 1 2 Keshavan, R. H.; Montanari, A.; Oh, S. (2010). "Matrix Completion from a Few Entries". IEEE Transactions on Information Theory . 56 (6): 2980–2998. arXiv: 0901.3150 . doi:10.1109/TIT.2010.2046205. S2CID   53504.
  12. 1 2 3 Jain, P.; Netrapalli, P.; Sanghavi, S. (2013). "Low-rank Matrix Completion using Alternating Minimization". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing. ACM. pp. 665–674. arXiv: 1212.0467 . doi:10.1145/2488608.2488693. ISBN   978-1-4503-2029-0. S2CID   447011.
  13. 1 2 Cai, J.-F.; Candès, E. J.; Shen, Z. (2010). "A Singular Value Thresholding Algorithm for Matrix Completion". SIAM Journal on Optimization . 20 (4): 1956–1982. arXiv: 0810.3286 . doi:10.1137/080738970. S2CID   1254778.
  14. 1 2 Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021). "Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints". Operations Research . 70 (6): 3321–3344. arXiv: 2009.10395 . doi:10.1287/opre.2021.2182. S2CID   221836263.
  15. Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021). "A New Perspective on Low-Rank Optimization". Optimization Online . arXiv: 2105.05947 .
  16. Nguyen, L.T.; Kim, J.; Kim, S.; Shim, B. (2019). "Localization of IoT Networks Via Low-Rank Matrix Completion". IEEE Transactions on Communications . 67 (8): 5833–5847. doi:10.1109/TCOMM.2019.2915226. S2CID   164605437.
  17. Mahindre, G.; Jayasumana, A.P.; Gajamannage, K.; Paffenroth, R. (2019). "On Sampling and Recovery of Topology of Directed Social Networks – A Low-Rank Matrix Completion Based Approach". 2019 IEEE 44th Conference on Local Computer Networks (LCN). IEEE. pp. 324–331. doi:10.1109/LCN44214.2019.8990707. ISBN   978-1-7281-1028-8. S2CID   211206354.