  Robust Principal Component Analysis (PCA) has received massive attention in
recent years. It aims to recover a low-rank matrix and a sparse matrix from
their sum. This paper proposes a novel nonconvex Robust PCA algorithm, coined
Riemannian CUR (RieCUR), which utilizes the ideas of Riemannian optimization
and robust CUR decompositions. This algorithm has the same computational
complexity as Iterated Robust CUR, which is currently state-of-the-art, but is
more robust to outliers. RieCUR is also able to tolerate a significant amount
of outliers, and is comparable to Accelerated Alternating Projections, which
has high outlier tolerance but worse computational complexity than the proposed
method. Thus, the proposed algorithm achieves state-of-the-art performance on
Robust PCA both in terms of computational complexity and outlier tolerance.
