Abstract
Recent advances in matrix completion enable data imputation in full-rankmatrices by exploiting low dimensional (nonlinear) latent structure. In thispaper, we develop a new model for high rank matrix completion (HRMC), togetherwith batch and online methods to fit the model and out-of-sample extension tocomplete new data. The method works by (implicitly) mapping the data into ahigh dimensional polynomial feature space using the kernel trick; importantly,the data occupies a low dimensional subspace in this feature space, even whenthe original data matrix is of full-rank. We introduce an explicitparametrization of this low dimensional subspace, and an online fittingprocedure, to reduce computational complexity compared to the state of the art.The online method can also handle streaming or sequential data and adapt tonon-stationary latent structure. We provide guidance on the sampling raterequired these methods to succeed. Experimental results on synthetic data andmotion capture data validate the performance of the proposed methods.