Matrix Completion
Also known as: Nuclear Norm Minimization, Collaborative Filtering via Low-Rank Recovery, Inductive Matrix Completion, Matris Tamamlama
Matrix Completion is a technique for recovering a low-rank matrix from a small, possibly random subset of its entries. Introduced by Emmanuel Candès and Benjamin Recht in 2009, it reformulates the problem as nuclear norm minimization — a convex surrogate for rank minimization — and provides theoretical guarantees that exact recovery is achievable when entries are observed uniformly at random and the matrix satisfies an incoherence condition.
Key highlights
- Provably exact recovery under mild conditions with a polynomial-time convex program
- Handles very high rates of missingness when the matrix is truly low-rank
- No prior knowledge of rank is required; the nuclear norm minimization implicitly finds it
- Strong theoretical guarantees rooted in random matrix theory and convex analysis
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use matrix completion when data can be organized as a matrix with systematically missing entries and there is reason to believe the true signal has low rank — for example, in recommender systems, genomics, social network analysis, and image recovery. Key assumptions are that entries are missing at random and the matrix satisfies an incoherence condition. It is not appropriate for matrices with structured or non-random missingness, very high-rank structure, or when the low-rank assumption is unjustified. Alternatives include MICE imputation for general missing data and NMF when non-negativity is required.
Strengths & limitations
- Provably exact recovery under mild conditions with a polynomial-time convex program
- Handles very high rates of missingness when the matrix is truly low-rank
- No prior knowledge of rank is required; the nuclear norm minimization implicitly finds it
- Strong theoretical guarantees rooted in random matrix theory and convex analysis
- Computational cost of semidefinite programming scales poorly with matrix dimensions
- Incoherence assumption may fail in real datasets with structured missingness or outliers
- Performance degrades when the true rank is not much smaller than the matrix dimensions
- Nuclear norm minimization can be sensitive to noise; robust variants add additional complexity
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
Is nuclear norm minimization the only way to solve matrix completion?
No. Alternating least squares (ALS) and gradient descent on factored forms (e.g., SGD on U and V such that M ≈ UV^T) are widely used in practice for scalability. However, these non-convex approaches lack the exact recovery guarantees of nuclear norm minimization and may converge to local minima without careful initialization.
How much data is needed for exact recovery?
Candès and Recht showed that approximately C·mu·r·n·log(n) observed entries suffice for an n×n rank-r matrix with incoherence parameter mu. In practice this means a low-rank matrix can often be recovered from a sample that is only a small multiple of its intrinsic degrees of freedom, which equals r(2n−r) for an n×n matrix.
What is the incoherence condition and why does it matter?
Incoherence measures how spread out the singular vectors are across the coordinate basis. A matrix with concentrated singular vectors — such as a rank-1 matrix that is nonzero only in one row — stores most of its information in a small set of entries. If those entries happen to be unobserved, recovery is impossible regardless of how many other entries are known.
Sources
- 1.Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 2). Matrix Completion. ScholarGate. https://scholargate.app/machine-learning/matrix-completion