  Recovering a low-rank matrix from highly corrupted measurements arises in
compressed sensing of structured high-dimensional signals (e.g., videos and
hyperspectral images among others). Robust principal component analysis (RPCA),
solved via principal component pursuit (PCP), recovers a low-rank matrix from
sparse corruptions that are of unknown value and support by decomposing the
observation matrix into two terms: a low-rank matrix and a sparse one,
accounting for sparse noise and outliers. In the more general setting, where
only a fraction of the data matrix has been observed, low-rank matrix recovery
is achieved by solving the compressive principle component pursuit (CPCP). Both
PCP and CPCP are well-studied convex programs, and numerous iterative
algorithms have been proposed for their optimisation. Nevertheless, these
algorithms involve singular value decomposition (SVD) at each iteration, which
renders their applicability challenging in the case of massive data. In this
paper, we propose a multilevel approach for the solution of PCP and CPCP
problems. The core principle behind our algorithm is to apply SVD in models of
lower-dimensionality than the original one and then lift its solution to the
original problem dimension. We show that the proposed algorithms are easy to
implement, converge at the same rate but with much lower iteration cost.
Numerical experiments on numerous synthetic and real problems indicate that the
proposed multilevel algorithms are several times faster than their original
counterparts, namely PCP and CPCP.
