Speedup Matrix Completion with Side Information: Application to Multi-Label Learning

In standard matrix completion theory, it is required to have at least O(n ln2 n) ob-served entries to perfectly recover a low-rank matrixM of size n × n, leading to a large number of observations when n is large. In many real tasks, side informa-tion in addition to the observed entries is often available. In this work, we develop a novel theory of matrix completion that explicitly explore the side information to reduce the requirement on the number of observed entries. We show that, un-der appropriate conditions, with the assistance of side information matrices, the number of observed entries needed for a perfect recovery of matrixM can be dra-matically reduced to O(lnn). We demonstrate the effectiveness of the proposed approach for matrix completion in transductive incomplete multi-label learning. 1