Leveraged Matrix Completion With Noise

Completing low-rank matrices from subsampled measurements has received much attention in the past decade. Existing works indicate that <tex-math notation="LaTeX">O(nrlog²(n))</tex-math> datums are required to theoretically secure the completion of an <tex-math notation="LaTeX">n × n</tex-math> noisy matrix of rank <tex-math notation="LaTeX">r</tex-math> with high probability, under some quite restrictive assumptions: 1) the underlying matrix must be incoherent and 2) observations follow the uniform distribution. The restrictiveness is partially due to ignoring the roles of the leverage score and the oracle information of each element. In this article, we employ the leverage scores to characterize the importance of each element and significantly relax assumptions to: 1) not any other structure assumptions are imposed on the underlying low-rank matrix and 2) elements being observed are appropriately dependent on their importance via the leverage score. Under these assumptions, instead of uniform sampling, we devise an ununiform/biased sampling procedure that can reveal the “importance” of each observed element. Our proofs are supported by a novel approach that phrases sufficient optimality conditions based on the Golfing scheme, which would be of independent interest to the wider areas. Theoretical findings show that we can provably recover an unknown <tex-math notation="LaTeX">n× n</tex-math> matrix of rank <tex-math notation="LaTeX">r</tex-math> from just about <tex-math notation="LaTeX">O(nrlog² (n))</tex-math> entries, even when the observed entries are corrupted with a small amount of noisy information. The empirical results align precisely with our theories.