  We study a data model in which the data matrix D can be expressed as D = L +
S + C, where L is a low rank matrix, S an element-wise sparse matrix and C a
matrix whose non-zero columns are outlying data points. To date, robust PCA
algorithms have solely considered models with either S or C, but not both. As
such, existing algorithms cannot account for simultaneous element-wise and
column-wise corruptions. In this paper, a new robust PCA algorithm that is
robust to simultaneous types of corruption is proposed. Our approach hinges on
the sparse approximation of a sparsely corrupted column so that the sparse
expansion of a column with respect to the other data points is used to
distinguish a sparsely corrupted inlier column from an outlying data point. We
also develop a randomized design which provides a scalable implementation of
the proposed approach. The core idea of sparse approximation is analyzed
analytically where we show that the underlying ell_1-norm minimization can
obtain the representation of an inlier in presence of sparse corruptions.
