Friday, December 16, 2011

Real-Time Principal Component Pursuit

Graeme Pope let me know that "[they] will make the source code available online as soon as [they] have clarified the licensing issues." Great! in the meantime, here is the paper:

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.

As soon as the implementation is available, it will also be featured in the Matrix Factorization Jungle Page.

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.

No comments: