Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
This work addresses computational bottlenecks in RPCA, a widely used tool for dimension reduction, by providing a faster algorithm that is incremental in its methodological innovation.
The authors tackled the computational inefficiency of robust principal component analysis (RPCA) by proposing a novel non-convex algorithm called Iterated Robust CUR (IRCUR), which uses CUR decomposition to accelerate low-rank estimation, resulting in dramatic improvements in computational efficiency over state-of-the-art methods as validated by numerical experiments on synthetic and real-world datasets.
Robust principal component analysis (RPCA) is a widely used tool for dimension reduction. In this work, we propose a novel non-convex algorithm, coined Iterated Robust CUR (IRCUR), for solving RPCA problems, which dramatically improves the computational efficiency in comparison with the existing algorithms. IRCUR achieves this acceleration by employing CUR decomposition when updating the low rank component, which allows us to obtain an accurate low rank approximation via only three small submatrices. Consequently, IRCUR is able to process only the small submatrices and avoid expensive computing on the full matrix through the entire algorithm. Numerical experiments establish the computational advantage of IRCUR over the state-of-art algorithms on both synthetic and real-world datasets.