Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach

We consider the problem of matrix completion with graphs as side information depicting the interrelations between variables. The key challenge lies in leveraging the graph’s similarity structure to enhance matrix recovery. Existing approaches, primarily based on graph Laplacian regularization, suffer from several limitations: (1) they focus only on the similarity between neighboring variables while overlooking long-range correlations, (2) they are highly sensitive to false edges in the graphs, and (3) they lack theoretical guarantees regarding statistical and computational complexities. To address these issues, we propose, in this paper, a novel graph-regularized matrix completion algorithm called GSGD, based on a preconditioned projected gradient descent approach. We demonstrate that GSGD effectively captures the higher-order correlation information behind the graphs and achieves superior robustness and stability against the false edges. Theoretically, we prove that GSGD achieves linear convergence to the global optimum with near-optimal sample complexity, providing the first theoretical guarantees for both recovery accuracy and efficacy in the perspective of nonconvex optimization. Experiments on both synthetic and real-world data validate that GSGD achieves superior accuracy and scalability compared with several popular alternatives. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: Y. Wang is grateful for the support of the National Natural Science Foundation of China Grant 12371513. K. Wang acknowledges support from the State Key Laboratory of Robotics Grant 2023-O28. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1169 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1169 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .