Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting

Matrix completion, recovering a low-rank matrix from a small number of its entries, is a significant problem in machine learning and data analysis. Existing fast algorithms often rely on assumptions about data distribution, and these assumptions do not always hold true for real-world data, a problem known as generative overfitting. Semi-random models, which allow some degree of adversarial entry selection, provide a more realistic setting, but efficient high-accuracy algorithms for semi-random matrix completion remained elusive.

This paper introduces a novel, efficient algorithm to solve the semi-random matrix completion problem. The method uses an iterative approach with adaptive reweighting to progressively recover the matrix, using techniques from optimization and graph theory. Crucially, the algorithm provides guarantees on accuracy even in noisy settings and achieves nearly-linear time complexity, substantially improving upon existing solutions. The new algorithm avoids the polynomial dependence on inverse accuracy and condition number found in previous work, opening up possibilities for high-precision matrix recovery in practical applications.