DOI

10.17077/etd.1jh8ig66

Document Type

Dissertation

Date of Degree

Spring 2018

Access Restrictions

Access restricted until 07/03/2019

Degree Name

PhD (Doctor of Philosophy)

Degree In

Applied Mathematical and Computational Sciences

First Advisor

Cai, Jianfeng

Second Advisor

Xu, Weiyu

First Committee Member

Jorgensen, Palle E. T.

Second Committee Member

Li, Tong

Third Committee Member

Ye, Yangbo

Abstract

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.

Pages

xii, 91 pages

Bibliography

Includes bibliographical references (pages 87-91).

Copyright

Copyright © 2018 HanQin Cai

Share

COinS