Classification with Low Rank and Missing Data
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.
Cite
Text
Hazan et al. "Classification with Low Rank and Missing Data." International Conference on Machine Learning, 2015.Markdown
[Hazan et al. "Classification with Low Rank and Missing Data." International Conference on Machine Learning, 2015.](https://mlanthology.org/icml/2015/hazan2015icml-classification/)BibTeX
@inproceedings{hazan2015icml-classification,
title = {{Classification with Low Rank and Missing Data}},
author = {Hazan, Elad and Livni, Roi and Mansour, Yishay},
booktitle = {International Conference on Machine Learning},
year = {2015},
pages = {257-266},
volume = {37},
url = {https://mlanthology.org/icml/2015/hazan2015icml-classification/}
}