Non-monotone Alternating Direction Methods For Robust Principal Component Analysis

Recently,massive amounts of high-dimensional data need to be analyzed and processed in science,engineering and society,such as images,video,multimedia data and biological data.To reduce the dimension and scale of the data,we must take advantage of the fact that such data have low intrinsic dimensionality.Therefore,robust principal component analysis is one of the hot topics in optimization research in recent years.Robust principal component analysis aims to decompose the observed data into low-rank part and sparse part,which is NP-hard because of the particularity of rank function and l0 norm.Convexization can establish provable theoretical guarantee.However,when the index set of nonzero entries in sparse part does not satisfy uniform distribution,algorithms for convex model can not solve practical problems well.In this thesis,we consider the non-convex model,and use the matrix factorization technique to reduce the entries of constraint conditions.Under the framework of alternating direction method,we propose two fast algorithms and analyze their convergence and numerical results.The basic structure of this thesis is as follows:In chapter 1,we describe the researching background,fundamental principles and corresponding mathematical models of robust principal component analysis,then briefly explain the main content of this thesis.In chapter 2,we focus on the non-convex model and design an alternating direction method equipped with a non-monotone search technique.The algorithm alternately solves optimization problems of low-rank and sparse variables.In each iteration,the variables of the low-rank part are updated by a gradient descent method with a variable step size,and the variables of the sparse part are updated by a non-monotone search technique.We establish the global convergence theory of the new algorithm under certain conditions.Considering the independence of the alternating direction method,we design a parallel algorithm and prove the global convergence under some weak assumptions in chapter 3.In chapter 4,we solve the robust principal component analysis on synthetic and real data sets show that parallelization significantly improves the computational efficiency.Compared with convex relaxation based methods,the proposed algorithm greatly reduces the computational complexity.