While the performance of Robust Principal Component Analysis (RPCA), in terms of the recovered low-rank matrices, is quite satisfactory to many applications, the time efﬁciency is not, especially for scalable data. We propose to solve this problem using a novel fast incremental RPCA (FRPCA) approach. The low rank matrices of the incrementally-observed data are estimated using a convex optimization model that exploits information obtained from the preestimated low-rank matrices of the original observations. The evaluation results supports the potential of FRPCA for fast, yet accurate, recovery of the low-rank matrices. The proposed FRPCA boosts the efﬁciency of the traditional RPCA by multiple hundreds of times, while scarifying less than 1% of accuracy.