Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
Abstract
We consider the problem of reconstructing a rank-one matrix from a revealed subset of its entries when some of the revealed entries are corrupted with perturbations that are unknown and can be arbitrarily large. It is not known which revealed entries are corrupted. We propose a new algorithm combining alternating minimization with extreme-value filtering and provide sufficient and necessary conditions to recover the original rank-one matrix. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an Erd\H os-R\'enyi random graph.
Cite
Text
Ma and Olshevsky. "Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion." Neural Information Processing Systems, 2020.Markdown
[Ma and Olshevsky. "Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/ma2020neurips-adversarial/)BibTeX
@inproceedings{ma2020neurips-adversarial,
title = {{Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion}},
author = {Ma, Qianqian and Olshevsky, Alex},
booktitle = {Neural Information Processing Systems},
year = {2020},
url = {https://mlanthology.org/neurips/2020/ma2020neurips-adversarial/}
}