Description
In this report we lower the bounds on the number of required sampled entries for reconstructing low- rank positive semidefinite matrices through nuclear norm minimization. We show for an n × n matrix of rank r only O(r n logn loglogn) samped entries are needed to complete the matrix as compared to previous work’s O(r n log^2 n) entries. We obtain this result by using rejection sampling when constructing a dual variable certificate.