Real-time principal component cursuit

Authors

Graeme Pope, Manuel Baumann, Christoph Studer, and Giuseppe Durisi

Reference

Proc. of Asilomar Conf. on Signals, Systems, and Computers (Asilomar), Pacific Grove, CA, pp. 1433-1437, Nov. 2011.

Abstract

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.

Download this document:

Copyright Notice: © 2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.