  In some significant applications such as data forecasting, the locations of
missing entries cannot obey any non-degenerate distributions, questioning the
validity of the prevalent assumption that the missing data is randomly chosen
according to some probabilistic model. To break through the limits of random
sampling, we explore in this paper the problem of real-valued matrix completion
under the setup of deterministic sampling. We propose two conditions, isomeric
condition and relative well-conditionedness, for guaranteeing an arbitrary
matrix to be recoverable from a sampling of the matrix entries. It is provable
that the proposed conditions are weaker than the assumption of uniform sampling
and, most importantly, it is also provable that the isomeric condition is
necessary for the completions of any partial matrices to be identifiable.
Equipped with these new tools, we prove a collection of theorems for missing
data recovery as well as convex/nonconvex matrix completion. Among other
things, we study in detail a Schatten quasi-norm induced method termed isomeric
dictionary pursuit (IsoDP), and we show that IsoDP exhibits some distinct
behaviors absent in the traditional bilinear programs.
