  This paper considers the use of Robust PCA in a CUR decomposition framework
and applications thereof. Our main algorithms produce a robust version of
column-row factorizations of matrices $\mathbf{D}=\mathbf{L}+\mathbf{S}$ where
$\mathbf{L}$ is low-rank and $\mathbf{S}$ contains sparse outliers. These
methods yield interpretable factorizations at low computational cost, and
provide new CUR decompositions that are robust to sparse outliers, in contrast
to previous methods. We consider two key imaging applications of Robust PCA:
video foreground-background separation and face modeling. This paper examines
the qualitative behavior of our Robust CUR decompositions on the benchmark
videos and face datasets, and find that our method works as well as standard
Robust PCA while being significantly faster. Additionally, we consider hybrid
randomized and deterministic sampling methods which produce a compact CUR
decomposition of a given matrix, and apply this to video sequences to produce
canonical frames thereof.
