INTRODUCTION
Surveillance video background subtraction is an extremely useful topic. Among existing techniques, Robust Principal Component Analysis (Robust PCA) stands out for its robustness against outliers. It is based on the traditional PCA which enables us finding and exploiting low‐rank structure in high‐dimensional data by converting possibly correlated variables into a set of linearly independent principal components. The classical PCA method, though, suffers from its lack of resistance to corruptions of individual input data points. RPCA overcomes this by taking care of the outlier terms and decompose the original matrix as the sum of a low rank component and a sparse error component.
However, the straight‐forward computation for RPCA takes O(n^6) complexity hence becoming unfeasible for large problems. Yuan and Yang (2009) proposed a more efficient algorithm having O(n^3) complexity. The key bottleneck in their algorithm is a QR factorization. In this project, we optimized this part using the Tall‐Skinny QR algorithm employing the technique of MPI and GPU computing. We enjoyed a 60× speedup.
CS 205 Final Project | Fall 2013 | Xueshan Zhang and Ming Zhu