This paper develops a new class of nonconvex regularizers for low-rank matrix recovery. Many regularizers are motivated as convex relaxations of the \emph{matrix rank} function. Our new factor group-sparse regularizers are motivated as a relaxation of the \emph{number of nonzero columns} in a factorization of the matrix. These nonconvex regularizers are sharper than the nuclear norm; indeed, we show they are related to Schatten-$p$ norms with arbitrarily small $0 < p \leq 1$. Moreover, these factor group-sparse regularizers can be written in a factored form that enables efficient and effective nonconvex optimization; notably, the method does not use singular value decomposition. We provide generalization error bounds for low-rank matrix completion which show improved upper bounds for Schatten-$p$ norm reglarization as $p$ decreases. Compared to the max norm and the factored formulation of the nuclear norm, factor group-sparse regularizers are more efficient, accurate, and robust to the initial guess of rank. Experiments show promising performance of factor group-sparse regularization for low-rank matrix completion and robust principal component analysis.

However, the proposed method and results do not have big impact in practical perspective because the convex regularized matrix factorization itself is very naive, and non-convex regularized low-rank matrix recovery is now widely studied and there are many related works such as truncated nuclear-norm[ex1], weighted nuclear-norm[ex2], capped-l1[ex3], LSP[ex4], SCAD[ex5], and MCP[ex6]. Also in another perspective, greedy rank-increment approach [ex7,ex8,ex9] for low-rank matrix recovery should be referred for discussion. This does not need to estimate initial d unlike regularized matrix factorization methods, and it is usually memory efficient.