  We introduce a reformulation of regularized low-rank recovery models to take
advantage of GPU, multiple CPU, and hybridized architectures. Low-rank recovery
often involves nuclear-norm minimization through iterative thresholding of
singular values. These models are slow to fit and difficult to parallelize
because of their dependence on computing a singular value decomposition at each
iteration. Regularized low-rank recovery models also incorporate non-smooth
terms to separate structured components (e.g. sparse outliers) from the
low-rank component, making these problems more difficult.
  Using Burer-Monteiro splitting and marginalization, we develop a smooth,
non-convex formulation of regularized low-rank recovery models that can be fit
with first-order solvers. We develop a computable certificate of convergence
for this non-convex program, and use it to establish bounds on the
suboptimality of any point. Using robust principal component analysis (RPCA) as
an example, we include numerical experiments showing that this approach is an
order-of-magnitude faster than existing RPCA solvers on the GPU. We also show
that this acceleration allows new applications for RPCA, including real-time
background subtraction and MR image analysis.
