A Deterministic Theory of Low Rank Matrix Completion

DOI10.1109/TIT.2020.3019569MaRDI QIDQ5138947zbMATH OpenOpenAlexFDO

Authors Sourav Chatterjee

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.01079

zbMATH Keywords

asymptotic solutiongraph limit theorymodification of Candès-Recht nuclear norm minimization algorithm

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Matrix completion problems (15A83)

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`es-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.

Cited in

(11)

• Low-rank matrix completion in a general non-orthogonal basis
• Matrix completion for matrices with low-rank displacement
• Completing any low-rank matrix, provably
• Low-Rank Matrix Completion in the Presence of High Coherence
• A universal rank approximation method for matrix completion
• Deterministic tensor completion with hypergraph expanders
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• Low-Complexity Modeling of Partially Available Second-Order Statistics: Theory and an Efficient Matrix Completion Algorithm
• A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm
• Nuclear norm regularization
• Robust Matrix Completion with Heavy-Tailed Noise

This page was built for publication: A Deterministic Theory of Low Rank Matrix Completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138947)