2019/10/30 by Simon Foucart, Deanna Needell, Foucart, Simon +7
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Target Tracking and Data Fusion in Sensor Networks
paper · pdf · doi:10.48550/arxiv.1910.13986
openalex publication_date 2019/10/30 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We study the matrix completion problem when the observation pattern is\ndeterministic and possibly non-uniform. We propose a simple and efficient\ndebiased projection scheme for recovery from noisy observations and analyze the\nerror under a suitable weighted metric. We introduce a simple function of the\nweight matrix and the sampling pattern that governs the accuracy of the\nrecovered matrix. We derive theoretical guarantees that upper bound the\nrecovery error and nearly matching lower bounds that showcase optimality in\nseveral regimes. Our numerical experiments demonstrate the computational\nefficiency and accuracy of our approach, and show that debiasing is essential\nwhen using non-uniform sampling patterns.\n