Timezone: »

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

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #97
in Applications -- Matrix and Tensor Factorization »
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.
Keywords: Matrix and Tensor Factorization · Denoising · Applications · Algorithms -> Collaborative Filtering; Algorithms -> Large Scale Learning; Applications
[ Paper]  [ Poster] 

Author Information

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

More from the Same Authors