Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms

ArXi:2401.08197v3 Announce Type: replace This paper considers the problem of completing a rating matrix based on sub-sampled matrix entries as well as observed social graphs and hypergraphs. We show that there exists a \emph{sharp threshold} on the sample probability for the task of exactly completing the rating matrix -- the task is achievable when the sample probability is above the threshold, and is impossible otherwise -- nstrating a phase transition phenomenon.