Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion

Understand

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{o}s-R\'enyi random graph.