Nonconvex deterministic matrix completion by projected gradient descent methods

doi:10.1016/j.jco.2026.102056

Nonconvex deterministic matrix completion by projected gradient descent methods

2026-05-01

0

PRE

AI

DOI：10.1016/j.jco.2026.102056

Original

Original request for help

Save

Abstract

En 中文

We investigate deterministic matrix completion problem where the goal is to recover a low-rank matrix from a few observed entries, with the sampling set chosen from a biregular sampling matrix. We analyze projected gradient descent (PGD) for a Burer-Monteiro least-squares formulation and prove linear convergence to the ground truth under suitable initialization, sufficient samples, and incoherence assumptions. The convergence rate of PGD depends on the condition number kappa of the ground-truth and it deteriorates in the ill-conditioned case where kappa is large. To address this issue, we examine a scaled variant of PGD, and derive similar convergence results that maintain a linear rate independent of the condition number. Numerical experiments, including image completion tasks, support our theory and show that deterministic methods can improve robustness and accuracy compared with probabilistic approaches. (c) 2026 Published by Elsevier Inc.

Keywords:

Deterministic sampling

Matrix completion

Projected gradient descent

Matrix decomposition

Biregular sampling matrix

Local curvature and smoothness

Nonconvex deterministic matrix completion by projected gradient descent methods

Abstract

Journal

Organization

Cited Papers