Classification with Low Rank and Missing Data

@InProceedings{pmlr-v37-hazan15,
  title = 	 {Classification with Low Rank and Missing Data},
  author = 	 {Hazan, Elad and Livni, Roi and Mansour, Yishay},
  booktitle = 	 {Proceedings of the 32nd International Conference on Machine Learning},
  pages = 	 {257--266},
  year = 	 {2015},
  editor = 	 {Bach, Francis and Blei, David},
  volume = 	 {37},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Lille, France},
  month = 	 {07--09 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v37/hazan15.pdf},
  url = 	 {https://proceedings.mlr.press/v37/hazan15.html},
  abstract = 	 {We consider classification and regression tasks where we have missing data and assume that the (clean) data resides in a low rank subspace. Finding a hidden subspace is known to be computationally hard. Nevertheless, using a non-proper formulation we give an efficient agnostic algorithm that classifies as good as the best linear classifier coupled with the best low-dimensional subspace in which the data resides. A direct implication is that our algorithm can linearly (and non-linearly through kernels) classify provably as well as the best classifier that has access to the full data.}
}