  This paper investigates the low-rank matrix completion (LRMC) problem from a
generic view. Unlike most existing work which focused on numerically recovering
exact or approximate missing matrix entries from the observed ones, the only
available information herein is the pattern (structure) of observed/missing
entries, and the observed entries are classified into two types, namely, fixed
zero entries and unknown generic entries. The problem is whether there exists a
matrix completion with a prescribed rank r for almost all values of the unknown
generic entries except for a set of zero measure, which is called the generic
low-rank matrix completion (GLRMC) problem. We first justify the existence of
genericity in the complex field for this problem, that is, depending on the
pattern of observed/missing entries, for almost all values of the unknown
generic entries, either the answer to that problem is yes, or the answer is no.
We then provide necessary and sufficient conditions for the feasibility of the
GLRMC with the constraint that the rank of the completion reduces at least one.
Afterward, we provide a sufficient condition and a necessary condition (which
we conjecture to be sufficient) for the general case. Based on them, two
randomized algorithms are proposed to determine upper and lower bounds for the
generic minimum rank of the matrix completions. Our approaches are based on the
algebraic geometry theory and the basis preservation principle discovered
herein. Finally, numerical experiments are given to corroborate the theoretical
findings and the effectiveness of the proposed algorithms.
