Matrix Co-completion for Multi-label Classification with Missing Features and Labels

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 σ(Zij) of generating label Yij, where σ(·) 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.