Optimization Online


Robust Principal Component Analysis using Facial Reduction

Shiqian Ma (sqma***at***math.ucdavis.edu)
Fei Wang (fewa***at***kth.se)
Linchuan Wei (l36wei***at***uwaterloo.ca)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

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 low-rank matrix and a sparse matrix so as to eliminate erratic noise (outliers). This problem is known to be NP-hard 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 low-rank component, and the 1 norm, to obtain a sparse component. This is a well-structured convex problem that can be efficiently solved by modern first-order methods. However, first-order methods often yield low accuracy solutions. In this paper, we propose a novel nonconvex reformulation of the original NP-hard 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 high-level 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 (Data-Mining )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Robust Optimization

Citation: Research Report

Download: [PDF]

Entry Submitted: 03/20/2018
Entry Accepted: 03/20/2018
Entry Last Modified: 03/20/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society