Matrix completion

A 3-by-3 matrix with 4 missing entries

In mathematics, matrix completion is the process of adding entries to a matrix which has some unknown or missing values.[1]

In general, given no assumptions about the nature of the entries, matrix completion is theoretically impossible, because the missing entries could be anything. However, given a few assumptions about the nature of the matrix, various algorithms allow it to be reconstructed.[1] Some of the most common assumptions made are that the matrix is low-rank, the observed entries are observed uniformly at random and the singular vectors are separated from the canonical vectors. A well known method for reconstructing low-rank matrices based on convex optimization of the nuclear norm was introduced by Emmanuel Candès and Benjamin Recht.[2]

See also

References

  1. ↑ 1.0 1.1 Charles R. Johnson "Matrix Completion Problems: A Survey", in Matrix Theory and Applications by Charles R. Johnson 1990 ISBN 0821801546 pagez 171–176
  2. ↑ Exact Matrix Completion via Convex Optimization by Candès, Emmanuel J. and Recht, Benjamin (2009) in Foundations of Computational Mathematics, 9 (6). pp. 717–772. ISSN 1615-3375