2014/12/26 by Shusen Wang, Tong Zhang, Wang, Shusen +3
Computer Science · Engineering · Mathematics · #Advanced Image Processing Techniques #FOS: Computer and information sciences #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1412.7938
openalex publication_date 2014/12/26 · arxiv created 2015/02/10 · arxiv updated 2015/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.