Math 2.0

Linear and multilinear algebra; matrix theory Matrix equations and groups Problem

Matrix completion

Builds on MatrixRank of a matrixSingular value

Problem

Let FF be a field and let m,n≥1m, n \ge 1 be integers. Let Ω\Omega be a set of positions (i,j)(i, j) with 1≤i≤m1 \le i \le m and 1≤j≤n1 \le j \le n. For each (i,j)∈Ω(i, j) \in \Omega, let a value Mij∈FM_{ij} \in F be given. Find an m×nm \times n matrix XX over FF such that Xij=MijX_{ij} = M_{ij} for all (i,j)∈Ω(i, j) \in \Omega and the rank of XX is as small as possible.

Remarks

Without more structure the problem has no unique answer: the entries outside Ω\Omega can be anything, so one asks for the completion of lowest rank. Low-rank completion is NP-hard in general. Over ℝ\R, a standard relaxation replaces the rank by the nuclear norm, the sum of the singular values of XX, which gives a convex problem. Candès and Recht proved in 2009 that nuclear norm minimization recovers the unknown matrix exactly with high probability, under some conditions. The matrix must have low rank and satisfy an incoherence condition, and enough entries must be sampled at random. Other versions ask for a completion that is positive semidefinite, or that has another prescribed property.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Matrix, concept, no evidence levelMatrixconceptRank of a matrix, concept, no evidence levelRank of a matrixconceptSingular value, concept, no evidence levelSingular valueconceptMatrix completion, problem, no evidence levelMatrix completionproblem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Matrix concept
  2. Rank of a matrix concept
  3. Singular value concept
  4. Matrix completion problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Matrix_completion
About this page
TagGB7K3PTPAR
URIm2://GB7K3PTPAR
Kindproblem
WritingW0 stub
MSC15A83, 65F55
StatusThis copy of the site has no build data. Run m2 status GB7K3PTPAR.
AboutRank of a matrix
UsesMatrix, Rank of a matrix, Singular value
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.