Research map / Learning theory and algorithms / Matrix and tensor methods

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Matrix completion and factorization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes orthogonal complement matrix completion (OCMC), which adds a nuclear-norm penalty on the orthogonal complement projection of the target matrix to handle incomplete side information, with PAC sample-complexity bounds and a linearized ADMM solver.

Problem

Matrix completion when side information about row and column spaces is incomplete rather than perfect, so the classical projection constraints on the target matrix do not hold.

Approach

Project the target matrix onto four orthogonal subspaces defined by available side information; the orthogonal complement projection P_{A⊥B⊥}(R) is low-rank even when side information is incomplete, so OCMC adds its nuclear norm as a regularizer alongside the full-matrix nuclear norm, with weight tied to side-information completeness.

Key results

• On MovieLens-100k at 10% training proportion, OCMC achieves RMSE 1.1503 versus 1.3053 for DirtyIMC and 1.8050 for FPC; at 90% it reaches 0.8625, best among compared methods.
• On the Yahoo Arts dataset, OCMC achieves the best AP in four of five sampling rates, e.g. 0.9596 at 90% sampling versus 0.9266 for DirtyIMC.
• Theory: sample complexity bound is min{O(P^2 log N / eps^2), O(X^2 sqrt(N) / eps^2)}, so it decreases roughly quadratically as side-information completeness increases.

Measured effects reported in the paper

Surprising findings

• Maxide's error stays high in the synthetic experiments because it imposes projection constraints based on incomplete side information, which excludes the true matrix from its feasible set.
• On the Yahoo Arts dataset, OCMC has the highest AP at 10% sampling and the lower-tier AP at 30-90% in some rows, not uniformly best; the paper reports four best and one second-best result across five rates.

Limitations

• Experiments are limited to synthetic data and two real-world settings, with relatively simple baselines and no neural methods.
• Convergence claims rely on convexity and standard ADMM results; the linearized subproblem approximation is not fully analyzed in the main text.
• Sample-complexity analysis assumes P is set to the nuclear norm of the orthogonal complement, which requires knowledge of R that is unavailable in practice.

Experimental setup

Datasets: synthetic low-rank matrices (100x100, rank 10) Yahoo web page classification (Arts and 10 other categories) MovieLens-100k

Benchmarks: MovieLens-100k Yahoo web page classification (Arts)

Metrics: relative Frobenius error average precision RMSE

Baselines: SVT Maxide DirtyIMC FPC FNNM

Builds on: nuclear norm minimization inductive matrix completion Dirty-IMC Rademacher complexity PAC bound

Closest papers by meaning

• A Sparse Interactive Model for Matrix Completion with Side Information (NeurIPS 2016 · similarity 0.90)
• High Rank Matrix Completion With Side Information (AAAI 2018 · similarity 0.89)
• Matrix Completion with Model-free Weighting (ICML 2021 · similarity 0.88)
• A Pairwise Pseudo-likelihood Approach for Matrix Completion with Informative Missingness (NeurIPS 2024 · similarity 0.88)
• RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.86)
• Generalization Analysis of Deep Non-linear Matrix Completion (ICML 2024 · similarity 0.85)