This paper deals with the problem of robust matrix completion -- retrieving a low-rank matrix and a sparse matrix from the compressed counterpart of their superposition. Though seemingly not an unresolved issue, we point out that the compressed matrix in our case is sampled in a deterministic pattern instead of those random ones on which existing studies depend. In fact, deterministic sampling is much more hardware-friendly than random ones. The limited resources on many platforms leave deterministic sampling the only choice to sense a matrix, resulting in the significance of investigating robust matrix completion with deterministic pattern. In such spirit, this paper proposes \textit{ restricted approximate $\infty$-isometry property} and proves that, if a \textit{ low-rank} and \textit{ incoherent} square matrix and certain deterministic sampling pattern satisfy such property and two existing conditions called \textit{ isomerism} and \textit{ relative well-conditionedness}, the exact recovery from its sampled counterpart grossly corrupted by a small fraction of outliers via convex optimization happens with very high probability.
Categories: cs.IT math.IT