We study the problem of symmetric positive semi-definite low-rank matrix completion (MC) with deterministic entry-dependent sampling. In particular, we consider rectified linear unit (ReLU) sampling, where only positive entries are observed, as well as a generalization to threshold-based sampling. We first empirically demonstrate that the landscape of this MC problem is not globally benign: Gradient descent (GD) with random initialization will generally converge to stationary points that are not globally optimal. Nevertheless, we prove that when the matrix factor with a small rank satisfies mild assumptions, the nonconvex objective function is geodesically strongly convex on the quotient manifold in a neighborhood of a planted low-rank matrix. Moreover, we show that our assumptions are satisfied by a matrix factor with i.i.d. Gaussian entries. Finally, we develop a tailor-designed initialization for GD to solve our studied formulation, which empirically always achieves convergence to the global minima. We also conduct extensive experiments and compare MC methods, investigating convergence and completion performance with respect to initialization, noise level, dimension, and rank.

对称半正定低秩矩阵完成问题进行研究，包括确定性依赖于矩阵元素的采样。首先通过实验证明该问题的全局最优点与梯度下降算法具有难以收敛的关系，但证明了在矩阵因子的秩较小且满足一定假设的情况下，非凸目标函数在一个低秩矩阵附近的商流形上是测地强凸的。此外，通过实验证明所提出的GD初始参数设计能够保证收敛到全局最小值。还进行广泛实验，比较了不同初始化、噪声水平、维度和秩对MC方法的收敛性和完成性能的影响。

使用ReLU采样的对称矩阵补全