### Introduction

Robust principle component pursuit (RPCP)
aims at decomposing a given data matrix additively into a low-rank
matrix and a sparse matrix. R2PCP
solves such a matrix decomposition problem by formulating the
least-squares problem subject to rank- and cardinality constraints as
follows:

The resulting constrained optimization problem is tackled by an
(inexact) alternating minimization scheme on the respective matrix
manifolds. The sparse matrix subproblem is solved based on sorting. On
the other hand, the low-rank subproblem is resolved by a Riemannian
optimization step on the fixed-rank matrix manifold. Once the Riemannian
gradient and Hessian of the objective are computed, a dogleg descent
path is constructed in the tangent space. This is followed by a
backtracking line search based on a projective retraction. It is proven
theoretically that the overall alternating minimization scheme attains
q-linear convergence under a second-order sufficient condition. Beyond
the (iterative) alternating minimization scheme, we also incorporate,
based on particular applications, a heuristic trimming procedure in
order to adjust r (i.e. the rank of A) and s (i.e. cardinality of B)
dynamically along the iterations.

**(Jump to download section)**

### Demo: Application to surveillance videos

Example 1: Background-foreground separation of video "airport". (a)
original frames; (b) background as low-rank component via R2PCP; (c)
foreground as sparse component via R2PCP; (d) background as low-rank
component via augmented Lagrangian method; (e) foreground as sparse
component via augmented Lagrangian method.

Example 2: Background-foreground separation of video "lobby". (a)
original frames; (b) background as low-rank component via R2PCP; (c)
foreground as sparse component via R2PCP; (d) background as low-rank
component via augmented Lagrangian method; (e) foreground as sparse
component via augmented Lagrangian method.

### Downloads

- R2PCP package

- Readme file

- Slide presentation

Please observe the disclaimer information below.

### Reference

M. Hintermüller and T. Wu, "Robust Principal Component Pursuit via
Inexact Alternating Minimization on Matrix Manifolds", Journal of
Mathematical Imaging and Vision, to appear.

DOI: 10.1007/s10851-014-0527-y. [link]
[pdf]

### Disclaimer

The R2PCP package was developed by Michael Hintermüller from
Department of Mathematics at the Humboldt-University of Berlin and
Tao Wu from Institute for Mathematics and Scientific Computing at
the University of Graz. This work is supported by the Austria
Science Fund (FWF) under START-program Y305 "Interfaces and Free
Boundaries" and the SFB F32 "Mathematical Optimization and
Applications in Biomedical Sciences".

The R2PCP package (including code modifications) may only be used
for NON-COMMERCIAL RESEARCH purposes. For inquiries concerning a
different use, please contact Prof. Michael Hintermüller from the Humboldt-University of Berlin.

Your comments are welcome. Please keep track of bugs or missing/
confusing instructions and report them to

Michael Hintermüller

Tao Wu

The algorithms contained in the R2PCP package were implemented by
Tao Wu.