David Aristoff's homepage
Title: Efficient robust PCA algorithms for the GPU
We introduce the matrix completion problem and the similar robust PCA (RPCA) problem and discuss their relation to compressed sensing and some of their applications to collaborative filtering, background detection in videos, and neuroscience. We cover some standard algorithms to solve these problems, including proximal gradient descent, Frank-Wolfe/conditional-gradient, and Burer-Monteiro splitting. A natural idea to speed up the algorithms is to run them on the GPU to take advantage of the many parallel threads of a GPU. This works well for some matrix completion algorithms, but the RPCA algorithms do not parallelize well. This motivates our new algorithm for RPCA which is designed to run well on the GPU, and we show results with major improvements over existing algorithms, even reaching real-time processing in some cases.