Matrix completion aims to recover missing entries in a data matrix using a subset of observed entries. Previous studies show that side information can greatly improve completion accuracy, but most assume perfect side information, which is rarely available in practice. In this paper, we propose an orthogonal complement matrix completion (OCMC) model to address the challenge of matrix completion with incomplete side information. The model leverages the orthogonal complement projection derived from the available side information, generalizing the traditional perfect side information matrix completion to the scenarios with incomplete side information. Moreover, using probably approximately correct (PAC) learning theory, we show that the sample complexity of OCMC model decreases quadratically with the completeness level. To efficiently solve the OCMC model, a linearized Lagrangian algorithm is developed with convergence guarantees. Experimental results show that the proposed OCMC model outperforms state-of-the-art methods on both synthetic data and real-world applications.

Many real-world systems, such as movie recommendation or multi-label tagging, rely on making predictions from partially observed data. Fortunately, extra information — such as user profiles or known relationships between labels — is often available to improve these predictions. However, this additional knowledge, known as side information, is typically incomplete in practice. To explore whether systems can still make better predictions using incomplete side information, we introduce a novel method called orthogonal complement matrix completion (OCMC). This method leverages the low-rank structure not only of the target data itself, but also of the part that is not captured by the available side information. When evaluated on both synthetic and real-world datasets, the proposed OCMC outperforms existing state-of-the-art methods, demonstrating that even incomplete side information can be effectively used to improve prediction accuracy.