  We consider a challenging multi-label classification problem where both
feature matrix $\X$ and label matrix $\Y$ have missing entries. An existing
method concatenated $\X$ and $\Y$ as $[\X; \Y]$ and applied a matrix completion
(MC) method to fill the missing entries, under the assumption that $[\X; \Y]$
is of low-rank. However, since entries of $\Y$ take binary values in the
multi-label setting, it is unlikely that $\Y$ is of low-rank. Moreover, such
assumption implies a linear relationship between $\X$ and $\Y$ which may not
hold in practice. In this paper, we consider a latent matrix $\Z$ that produces
the probability $\sigma(Z_{ij})$ of generating label $Y_{ij}$, where
$\sigma(\cdot)$ is nonlinear. Considering label correlation, we assume $[\X;
\Z]$ is of low-rank, and propose an MC algorithm based on subgradient descent
named co-completion (COCO) motivated by elastic net and one-bit MC. We give a
theoretical bound on the recovery effect of COCO and demonstrate its practical
usefulness through experiments.
