  Many practical problems involve the recovery of a binary matrix from partial
information, which makes the binary matrix completion (BMC) technique received
increasing attention in machine learning. In particular, we consider a special
case of BMC problem, in which only a subset of positive elements can be
observed. In recent years, convex regularization based methods are the
mainstream approaches for this task. However, the applications of nonconvex
surrogates in standard matrix completion have demonstrated better empirical
performance. Accordingly, we propose a novel BMC model with nonconvex
regularizers and provide the recovery guarantee for the model. Furthermore, for
solving the resultant nonconvex optimization problem, we improve the popular
proximal algorithm with acceleration strategies. It can be guaranteed that the
convergence rate of the algorithm is in the order of ${1/T}$, where $T$ is the
number of iterations. Extensive experiments conducted on both synthetic and
real-world data sets demonstrate the superiority of the proposed approach over
other competing methods.
