  


Robust Principal Component Analysis using Facial Reduction
Shiqian Ma (sqmamath.ucdavis.edu) Abstract: We study algorithms for robust principal component analysis (RPCA) for a partially observed data matrix. The aim is to recover the data matrix as a sum of a lowrank matrix and a sparse matrix so as to eliminate erratic noise (outliers). This problem is known to be NPhard in general. A classical way to solve RPCA is to consider convex relaxations, e.g., to minimize the sum of the nuclear norm, to obtain a lowrank component, and the 1 norm, to obtain a sparse component. This is a wellstructured convex problem that can be efficiently solved by modern firstorder methods. However, firstorder methods often yield low accuracy solutions. In this paper, we propose a novel nonconvex reformulation of the original NPhard RPCA model. The new model imposes a semidefinite cone constraint and utilizes a facial reduction technique. we are thus able to reduce the size significantly. This makes the problem amenable to efficient algorithms in order to obtain highlevel accuracy. We include numerical results that confirm the efficacy of our approach. Keywords: Robust Principal Component Analysis, Semidefinite Cone, Facial Reduction, Biclique Category 1: Applications  Science and Engineering (DataMining ) Category 2: Linear, Cone and Semidefinite Programming Category 3: Robust Optimization Citation: Research Report Download: [PDF] Entry Submitted: 03/20/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  