Efficient Data Completion and Augmentation

Fast data completion and augmentation methods with provable theoretical guarantees enable efficient and reliable data analysis. Many datasets can be represented as real-valued matrices and filled using matrix completion (MC) methods. This paper proposes a novel two-step approach for matrix recovery involving the sequential solution of convex optimization tasks. Firstly, a subset of columns is randomly chosen, and the matrix is completed using a nuclear norm minimization algorithm. Secondly, we solve the least squares problem by incorporating the known elements and the completed columns. We introduce three algorithms for implementing our Columns Selected Matrix Completion (CSMC) method, tailored to different problem sizes. Provided necessary assumptions and the probability of achieving accurate solutions are validated through extensive numerical experiments. Synthetic data experiments assess the method's performance regarding matrix size, rank, and missing element proportion. Evaluation in image completion and graph link prediction demonstrates that CSMC provides comparable solution quality to state-of-the-art convex optimization-based MC algortthms while significantly reduciny computation time.