Adjusting Leverage Scores by Row Weighting: A Practical Approach to Coherent Matrix Completion
This addresses a key limitation in low-rank matrix completion for applications requiring coherent data, though it is incremental as it builds on prior weighted nuclear norm minimization ideas.
The paper tackles the problem of coherent matrix completion under uniform sampling, where existing methods fail, and presents a practical weighting method that enables successful recovery of highly coherent matrices with high precision in experiments.
Low-rank matrix completion is an important problem with extensive real-world applications. When observations are uniformly sampled from the underlying matrix entries, existing methods all require the matrix to be incoherent. This paper provides the first working method for coherent matrix completion under the standard uniform sampling model. Our approach is based on the weighted nuclear norm minimization idea proposed in several recent work, and our key contribution is a practical method to compute the weighting matrices so that the leverage scores become more uniform after weighting. Under suitable conditions, we are able to derive theoretical results, showing the effectiveness of our approach. Experiments on synthetic data show that our approach recovers highly coherent matrices with high precision, whereas the standard unweighted method fails even on noise-free data.