robust principal component analysis

Robust Principal Component Analysis using Facial Reduction

Published: 2018/03/20

Data-Mining, Linear, Cone and Semidefinite Programming, Robust Optimization biclique, facial reduction, robust principal component analysis, semidefinite cone

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 … Read more

Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

Published: 2009/12/22, Updated: 2012/06/14

Donald Goldfarb

Shiqian Ma

Katya Scheinberg

Convex and Nonsmooth Optimization alternating direction method, alternating linearization method, augmented lagrangian method, convex optimization, gauss-seidel method, optimal gradient method, peaceman-rachford method, proximal point algorithm, robust principal component analysis, variable splitting

We present in this paper first-order alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/\sqrt{\epsilon})$ iterations, with little change in … Read more