  Low-rank matrix completion is a problem of immense practical importance.
Recent works on the subject often use nuclear norm as a convex surrogate of the
rank function. Despite its solid theoretical foundation, the convex version of
the problem often fails to work satisfactorily in real-life applications. Real
data often suffer from very few observations, with support not meeting the
random requirements, ubiquitous presence of noise and potentially gross
corruptions, sometimes with these simultaneously occurring.
  This paper proposes a Proximal Alternating Robust Subspace Minimization
(PARSuMi) method to tackle the three problems. The proximal alternating scheme
explicitly exploits the rank constraint on the completed matrix and uses the
$\ell_0$ pseudo-norm directly in the corruption recovery step. We show that the
proposed method for the non-convex and non-smooth model converges to a
stationary point. Although it is not guaranteed to find the global optimal
solution, in practice we find that our algorithm can typically arrive at a good
local minimizer when it is supplied with a reasonably good starting point based
on convex optimization. Extensive experiments with challenging synthetic and
real data demonstrate that our algorithm succeeds in a much larger range of
practical problems where convex optimization fails, and it also outperforms
various state-of-the-art algorithms.
