Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection

Gengshuo Chang, Wei Zhang, Lehan Zhang
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:7393-7416, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-chang25e, title = {Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection}, author = {Chang, Gengshuo and Zhang, Wei and Zhang, Lehan}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {7393--7416}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/chang25e/chang25e.pdf}, url = {https://proceedings.mlr.press/v267/chang25e.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection %A Gengshuo Chang %A Wei Zhang %A Lehan Zhang %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-chang25e %I PMLR %P 7393--7416 %U https://proceedings.mlr.press/v267/chang25e.html %V 267 %X 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.
APA
Chang, G., Zhang, W. & Zhang, L.. (2025). Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:7393-7416 Available from https://proceedings.mlr.press/v267/chang25e.html.

Related Material