Matrix rigidity and the ill-posedness of Robust PCA and matrix completion

Jared Tanner, Andrew Thompson, Simon Vary

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…