  In this work, we develop and analyze a Gradient Descent (GD) based solution,
called Alternating GD and Minimization (AltGDmin), for efficiently solving the
low rank matrix completion (LRMC) in a federated setting. LRMC involves
recovering an $n \times q$ rank-$r$ matrix $\Xstar$ from a subset of its
entries when $r \ll \min(n,q)$. Our theoretical guarantees (iteration and
sample complexity bounds) imply that AltGDmin is the most
communication-efficient solution in a federated setting, is one of the fastest,
and has the second best sample complexity among all iterative solutions to
LRMC. In addition, we also prove two important corollaries. (a) We provide a
guarantee for AltGDmin for solving the noisy LRMC problem. (b) We show how our
lemmas can be used to provide an improved sample complexity guarantee for
AltMin, which is the fastest centralized solution.
