Poster
Factor Group-Sparse Regularization for Efficient Low-Rank Matrix Recovery
Jicong Fan · Lijun Ding · Yudong Chen · Madeleine Udell

Wed Dec 11th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #97
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.

Author Information

Jicong Fan (Cornell University)
Lijun Ding (Cornell University)
Yudong Chen (Cornell University)
Madeleine Udell (Cornell University)

More from the Same Authors