Online High Rank Matrix Completion

Jicong Fan, Madeleine Udell; Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 8690-8698

Recent advances in matrix completion enable data imputation in full-rank matrices by exploiting low dimensional (nonlinear) latent structure. In this paper, we develop a new model for high rank matrix completion (HRMC), together with batch and online methods to fit the model and out-of-sample extension to complete new data. The method works by (implicitly) mapping the data into a high dimensional polynomial feature space using the kernel trick; importantly, the data occupies a low dimensional subspace in this feature space, even when the original data matrix is of full-rank. The online method can handle streaming or sequential data and adapt to non-stationary latent structure, and enjoys much lower space and time complexity than previous methods for HRMC. For example, the time complexity is reduced from O(n^3) to O(r^3), where n is the number of data points, r is the matrix rank in the feature space, and r<< n. We also provide guidance on sampling rate required for these methods to succeed. Experimental results on synthetic data and motion data validate the performance of the proposed methods.