  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.
