  We consider the low rank matrix completion problem over finite fields. This
problem has been extensively studied in the domain of real/complex numbers,
however, to the best of authors' knowledge, there exists merely one efficient
algorithm to tackle the problem in the binary field, due to Saunderson et al.
[1]. In this paper, we improve upon the theoretical guarantees for the
algorithm provided in [1]. Furthermore, we formulate a new graphical model for
the matrix completion problem over the finite field of size $q$, $\Bbb{F}_q$,
and present a message passing (MP) based approach to solve this problem. The
proposed algorithm is the first one for the considered matrix completion
problem over finite fields of arbitrary size. Our proposed method has a
significantly lower computational complexity, reducing it from $O(n^{2r+3})$ in
[1] down to $O(n^2)$ (where, the underlying matrix has dimension $n \times n$
and $r$ denotes its rank), while also improving the performance.
