Date of Degree
Access restricted until 07/03/2019
PhD (Doctor of Philosophy)
Applied Mathematical and Computational Sciences
First Committee Member
Palle E. T. Jorgensen
Second Committee Member
Third Committee Member
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  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.
xii, 91 pages
Includes bibliographical references (pages 87-91).
Copyright © 2018 HanQin Cai
Cai, HanQin. "Accelerating truncated singular-value decomposition: a fast and provable method for robust principal component analysis." PhD (Doctor of Philosophy) thesis, University of Iowa, 2018.
Available for download on Wednesday, July 03, 2019