High Rank Matrix Completion with Adaptive Neighbor Graphs

Matrix completion is a method for imputing missing data, typically based on the assumption of a low-rank structure. However, in practice, various factors can obscure this structure, leading to a perceived high-rank nature. Recently, a few studies begin to address high-rank data completion, their methods rely on specific hypothesis distributions that are often impractical to validate in real-world scenarios. Therefore, in this paper, we tackle high-rank data completion without any hypothesis distribution. Firstly, we theoretically demonstrate that the Radial Basis Function (RBF) kernel feature mapping has the capability to transform general high-rank data into low-rank data in a higher-dimensional feature space. Secondly, combining with the adaptive row and column neighbor information, a novel graph-based high-rank matrix completion algorithm is developed. Thirdly, experiments on four real datasets across three domains demonstrate that the proposed method reduces reconstruction error by up to 63% compared to the second-best method at the same missing rate. Furthermore, to achieve similar accuracy, it requires up to 40% fewer samples. Our code is released at https://github.com/shiqinyeah/Graph-HRMC.git.