  The stable principal component pursuit (SPCP) is a non-smooth convex
optimization problem, the solution of which enables one to reliably recover the
low rank and sparse components of a data matrix which is corrupted by a dense
noise matrix, even when only a fraction of data entries are observable. In this
paper, we propose a new algorithm for solving SPCP. The proposed algorithm is a
modification of the alternating direction method of multipliers (ADMM) where we
use an increasing sequence of penalty parameters instead of a fixed penalty.
The algorithm is based on partial variable splitting and works directly with
the non-smooth objective function. We show that both primal and dual iterate
sequences converge under mild conditions on the sequence of penalty parameters.
To the best of our knowledge, this is the first convergence result for a
variable penalty ADMM when penalties are not bounded, the objective function is
non-smooth and its sub-differential is not uniformly bounded. Using partial
variable splitting and adopting an increasing sequence of penalty multipliers,
together, significantly reduce the number of iterations required to achieve
feasibility in practice. Our preliminary computational tests show that the
proposed algorithm works very well in practice, and outperforms ASALM, a state
of the art ADMM algorithm for the SPCP problem with a constant penalty
parameter.
