  Robust Principal Component Analysis (PCA) (Candes et al., 2011) and low-rank
matrix completion (Recht et al., 2010) are extensions of PCA to allow for
outliers and missing entries respectively. It is well-known that solving these
problems requires a low coherence between the low-rank matrix and the canonical
basis, since in the extreme cases -- when the low-rank matrix we wish to
recover is also sparse -- there is an inherent ambiguity. However, the
well-posedness issue in both problems is an even more fundamental one: in some
cases, both Robust PCA and matrix completion can fail to have any solutions at
due to the set of low-rank plus sparse matrices not being closed, which in turn
is equivalent to the notion of the matrix rigidity function not being lower
semicontinuous (Kumar et al., 2014). By constructing infinite families of
matrices, we derive bounds on the rank and sparsity such that the set of
low-rank plus sparse matrices is not closed. We also demonstrate numerically
that a wide range of non-convex algorithms for both Robust PCA and matrix
completion have diverging components when applied to our constructed matrices.
An analogy can be drawn to the case of sets of higher order tensors not being
closed under canonical polyadic (CP) tensor rank, rendering the best low-rank
tensor approximation unsolvable (De Silva and Lim, 2008) and hence encourage
the use of multilinear tensor rank (De Lathauwer, 2000).
