Back to Search
Start Over
A Deterministic Theory of Low Rank Matrix Completion.
- Source :
- IEEE Transactions on Information Theory; Dec2020, Vol. 66 Issue 12, p8046-8055, 10p
- Publication Year :
- 2020
-
Abstract
- The problem of completing a large low rank matrix using a subset of revealed entries has received much attention in the last ten years. The main result of this paper gives a necessary and sufficient condition, stated in the language of graph limit theory, for a sequence of matrix completion problems with arbitrary missing patterns to be asymptotically solvable. It is then shown that a small modification of the Candès–Recht nuclear norm minimization algorithm provides the required asymptotic solution whenever the sequence of problems is asymptotically solvable. The theory is fully deterministic, with no assumption of randomness. A number of open questions are listed. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPH theory
LOW-rank matrices
ALGORITHMS
LINEAR algebra
LANGUAGE policy
YEAR
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 66
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 147291940
- Full Text :
- https://doi.org/10.1109/TIT.2020.3019569