Relaxed leverage sampling for low-rank matrix completion

We show that any m×n matrix of rank ϱ can be recovered exactly via nuclear norm minimization from Θ(λ⋅log2(m+n)) randomly sampled entries (λ=(m+n)ϱ−ϱ2 being the degrees of freedom), if we observe each entry with probability proportional to the sum of corresponding row and column leverage scores, minus their product. This relaxation in probabilities (as opposed to sum of leverage scores in [1]) can give us O(ϱ2log2(m+n)) additive improvement on the (best known) sample size of [1]. Further, we can use our relaxed leverage score sampling to achieve additive improvement on sample size for exact recovery of (a) incoherent matrices (with restricted leverage scores), and (b) row (or column) incoherent matrices, without knowing the leverage scores a priori.