Imperial College London


Faculty of EngineeringDepartment of Computing

Professor in Machine Learning & Computer Vision



+44 (0)20 7594 8461s.zafeiriou Website CV




375Huxley BuildingSouth Kensington Campus






BibTex format

author = {Hovhannisyan, V and Panagakis, I and Parpas, P and Zafeiriou, S},
doi = {10.1137/17M1178346},
journal = {SIAM Journal on Imaging Sciences},
pages = {624--649},
title = {Fast multilevel algorithms for compressive principal component pursuit},
url = {},
volume = {12},
year = {2019}

RIS format (EndNote, RefMan)

AB - 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 principal component pursuit (CPCP). Both PCP and CPCP are well-studied convex programs, and numerousiterative 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. Hence, our methods rely on the assumption that the low rank component can be represented in a lower dimensional space. 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.
AU - Hovhannisyan,V
AU - Panagakis,I
AU - Parpas,P
AU - Zafeiriou,S
DO - 10.1137/17M1178346
EP - 649
PY - 2019///
SN - 1936-4954
SP - 624
TI - Fast multilevel algorithms for compressive principal component pursuit
T2 - SIAM Journal on Imaging Sciences
UR -
UR -
VL - 12
ER -