Scalable Dynamic Matrix Completion for Information Processing and Link Discovery

We investigate a problem of significant practical importance, namely, the recovery of the data matrix from a partial set of its entries that are collected in a noisy environment (i.e., a noisy partial matrix). Our proposed Near-Optimal Matrix Completion (NOMC) target to provide a leading approach that can improve the matrix completion accuracy. Two types of data matrix are considered. The first type is that the matrix is low rank or can be explicitly transferred to a low rank, i.e., a Euclidean distance matric converted from object locations. Our primarily experimental results for such a type demonstrate that NOMC recovers a low-rank matrix with only 10% samples while achieving the Frobenius error less than 10%. The second type is that the matrix is high rank, such as an arbitrary image. Our initial result shows that NOMC reconstructs the original image with high quality from the downsampled image while 50% image pixels are randomly removed. This also says that NOMC could reconstruct the image clearly even if 50% image pixels are randomly lost, removed, contaminated, or corrupted. In this work, our works encompass the theoretical analysis and the development of the NOMC software product.