  Low-rank modeling has many important applications in computer vision and
machine learning. While the matrix rank is often approximated by the convex
nuclear norm, the use of nonconvex low-rank regularizers has demonstrated
better empirical performance. However, the resulting optimization problem is
much more challenging. Recent state-of-the-art requires an expensive full SVD
in each iteration. In this paper, we show that for many commonly-used nonconvex
low-rank regularizers, a cutoff can be derived to automatically threshold the
singular values obtained from the proximal operator. This allows such operator
being efficiently approximated by power method. Based on it, we develop a
proximal gradient algorithm (and its accelerated variant) with inexact proximal
splitting and prove that a convergence rate of O(1/T) where T is the number of
iterations is guaranteed. Furthermore, we show the proposed algorithm can be
well parallelized, which achieves nearly linear speedup w.r.t the number of
threads. Extensive experiments are performed on matrix completion and robust
principal component analysis, which shows a significant speedup over the
state-of-the-art. Moreover, the matrix solution obtained is more accurate and
has a lower rank than that of the nuclear norm regularizer.
