Matrix Completion from General Deterministic Sampling Patterns
Most of the existing works on provable guarantees for low-rank matrix completion algorithms rely on some unrealistic assumptions such that matrix entries are sampled randomly or the sampling pattern has a specific structure. In this work, we establish theoretical guarantee for the exact and approximate low-rank matrix completion problems which can be applied to any deterministic sampling schemes. For this, we introduce a graph having observed entries as its edge set, and investigate its graph properties involving the performance of the standard constrained nuclear norm minimization algorithm. We theoretically and experimentally show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees. Our result can be viewed as an extension of the works by Bhojanapalli and Jain [2014] and Burnwal and Vidyasagar [2020], in which the node degrees of the observation graph were assumed to be the same. In particular, our theory significantly improves their results when the underlying matrix is symmetric.
Code (0)
등록된 구현이 없습니다.
Tasks
Low-Rank Matrix CompletionMatrix CompletionSimilar Papers 제목 키워드 기반
On Deterministic Sampling Patterns for Robust Low-Rank Matrix Completion
In this letter, we study the deterministic sampling patterns for the completion of low rank matrix, when corrupted with a sparse noise, also known as robust matrix completion. We extend the recent results on the determin…
Low-Rank Matrix CompletionMatrix CompletionvalidA Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions…
Low-Rank Matrix CompletionMatrix CompletionSpectral gap-based deterministic tensor completion
Tensor completion is a core machine learning algorithm used in recommender systems and other domains with missing data. While the matrix case is well-understood, theoretical results for tensor problems are limited, parti…
Recommendation SystemsRank Determination for Low-Rank Data Completion
Recently, fundamental conditions on the sampling patterns have been obtained for finite completability of low-rank matrices or tensors given the corresponding ranks. In this paper, we consider the scenario where the rank…
A New Theory for Matrix Completion
Prevalent matrix completion theories reply on an assumption that the locations of the missing data are distributed uniformly and randomly (i.e., uniform sampling). Nevertheless, the reason for observations being missing …
Matrix Completion