This paper presents the theoretical foundation of matrix completion, focusing on the minimum number of entries required to recover a matrix of rank r exactly. It shows that under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convex program—nuclear norm minimization—as soon as the number of entries is on the order of the information-theoretic limit (up to logarithmic factors). The paper demonstrates that nuclear norm minimization can recover a random n×n matrix of rank r with a number of samples on the order of nr log n, and that it succeeds as soon as the number of entries is of the form nr polylog(n). The paper also introduces the concept of strong incoherence, which is a condition on the singular vectors of the matrix that ensures the success of nuclear norm minimization. It provides several models of matrices that satisfy this condition, including uniformly bounded orthogonal models, low-rank low-coherence models, and random orthogonal models. The paper proves two main results: one showing that nuclear norm minimization can recover a matrix with high probability when the number of samples is on the order of nr log n, and another showing that it can recover a matrix with high probability when the number of samples is on the order of nr polylog(n). The paper also provides lower bounds on the number of samples required for matrix completion, showing that the number of samples must be at least proportional to the number of degrees of freedom of the matrix. The paper concludes that nuclear norm minimization is a powerful and efficient method for matrix completion, and that it can recover matrices with high probability under certain conditions.This paper presents the theoretical foundation of matrix completion, focusing on the minimum number of entries required to recover a matrix of rank r exactly. It shows that under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convex program—nuclear norm minimization—as soon as the number of entries is on the order of the information-theoretic limit (up to logarithmic factors). The paper demonstrates that nuclear norm minimization can recover a random n×n matrix of rank r with a number of samples on the order of nr log n, and that it succeeds as soon as the number of entries is of the form nr polylog(n). The paper also introduces the concept of strong incoherence, which is a condition on the singular vectors of the matrix that ensures the success of nuclear norm minimization. It provides several models of matrices that satisfy this condition, including uniformly bounded orthogonal models, low-rank low-coherence models, and random orthogonal models. The paper proves two main results: one showing that nuclear norm minimization can recover a matrix with high probability when the number of samples is on the order of nr log n, and another showing that it can recover a matrix with high probability when the number of samples is on the order of nr polylog(n). The paper also provides lower bounds on the number of samples required for matrix completion, showing that the number of samples must be at least proportional to the number of degrees of freedom of the matrix. The paper concludes that nuclear norm minimization is a powerful and efficient method for matrix completion, and that it can recover matrices with high probability under certain conditions.