Real-Time Principal Component Pursuit by Graeme Pope, Manuel Baumann, Christoph Studer, and Giuseppe Durisi. The abstract reads:
Robust principal component analysis (RPCA) deals with the decomposition of a matrix into a low-rank matrix and a sparse matrix. Such decompositions find, for example, applications in video surveillance or face recognition. One effective way to solve RPCA problems is to use a convex optimization method known as principal component pursuit (PCP). The corresponding algorithms have, however, prohibitive computational complexity for certain applications that require real-time processing. In this paper, we propose a variety of methods that significantly reduce computational complexity. Furthermore, we perform a systematic analysis of the performance/complexity tradeoffs underlying PCP. For synthetic data, we show that our methods result in a speedup of more than 365 times compared to a base C implementation at only a small loss in terms of recovery performance. In order to demonstrate the effectiveness of our approach, we consider foreground/background separation for video surveillance, where our methods enable real-time processing of a 640×480 color video stream at 10 frames per second (fps) using an off-the-shelf PC.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.