We give an online algorithm and prove novel mistake and regret bounds for online binary matrix completion with side information. The mistake bounds we prove are of the form \tilde{O}(D/\gamma^2). The term 1/\gamma^2 is analogous to the usual margin term in SVM (perceptron) bounds. More specifically, if we assume that there is some factorization of the underlying m x n matrix into PQ^T, where the rows of P are interpreted as classifiers in R^d and the rows of Q as instances in R^d, then gamma is the maximum (normalized) margin over all factorizations PQ^T consistent with the observed matrix. The quasi-dimension term D measures the quality of side information.

Weaknesses: The title is not appropriate. It actually talks about "binary matrix completion" instead of classical matrix completion. The paper is not reader-friendly. There is a lot of thing unexplained in the paper. For example, what is the motivation for the two proposed algorithms, and why they are reasonable to solve the current problem is not discussed.

We give an online algorithm and prove novel mistake and regret bounds for online binary matrix completion with side information. The mistake bounds we prove are of the form \tilde{O}(D/\gamma 2). The term 1/\gamma 2 is analogous to the usual margin term in SVM (perceptron) bounds. More specifically, if we assume that there is some factorization of the underlying m x n matrix into PQ T, where the rows of P are interpreted as "classifiers" in R d and the rows of Q as "instances" in R d, then gamma is the maximum (normalized) margin over all factorizations PQ T consistent with the observed matrix. The quasi-dimension term D measures the quality of side information.

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. We introduce an explicit parametrization of this low dimensional subspace, and an online fitting procedure, to reduce computational complexity compared to the state of the art. The online method can also handle streaming or sequential data and adapt to non-stationary latent structure. We provide guidance on the sampling rate required these methods to succeed. Experimental results on synthetic data and motion capture data validate the performance of the proposed methods.