Accelerating truncated singular-value decomposition: a fast and provable method for robust principal component analysis

Principal component analysis (PCA) is one of the most popular statistical procedures for dimension reduction. A modification of PCA, called robust principal component analysis (RPCA), has been studied to overcome the well-known shortness of PCA: sensitivity to outliers and corrupted data points. Earlier works have proved RPCA can be exactly recovered via semidenite programming. Recently, researchers have provided some provable non-convex solvers for RPCA, based on projected gradient descent or alternating projections, in full or partial observed settings. Yet, we nd the computational complexity of the recent RPCA algorithms can be improved further. We study RPCA in the fully observed setting, which is about separating a low rank matrix L and a sparse matrix S from their given sum D = L + S. In this thesis, a new non-convex algorithm, dubbed accelerated alternating projections, is introduced for solving RPCA rapidly. The proposed new algorithm signicantly improves the computational efficiency of the existing alternating projections based algorithm proposed in [1] when updating the estimate of low rank factor. The acceleration is achieved by rst projecting a matrix onto some low dimensional subspace before obtaining a new estimate of the low rank matrix via truncated singular-value decomposition. Essentially, truncated singular-value decomposition (a.k.a. the best low rank approximation) is replaced by a high-efficiency sub-optimal low rank approximation, while the convergence is retained. Exact recovery guarantee has been established, which shows linear convergence of the proposed algorithm under certain natural assumptions. Empirical performance evaluations establish the advantage of our algorithm over other state-of-the-art algorithms for RPCA. An application experiment on video background subtraction has been also established.