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. These results
are then applied to the problem of classification from crowdsourced data under
the assumption that while the majority of the workers are governed by the
standard single-coin David-Skene model (i.e., they output the correct answer
with a certain probability), some of the workers can deviate arbitrarily from
this model. In particular, the "adversarial" workers could even make decisions
designed to make the algorithm output an incorrect answer. Extensive
experimental results show our algorithm for this problem, based on rank-one
matrix completion with perturbations, outperforms all other state-of-the-art
methods in such an adversarial scenario.

本文提出一种用于从受损数据修复秩为一矩阵的算法，特别针对带有任意大干扰的众包数据分类问题，通过交替最小化与极值过滤相结合，本文提供了充分必要的条件，可以在明确哪些信息受到损坏的情况下进行完美修复，并且在 “对抗” 情景下击败了所有现有算法。

通过强健的秩一矩阵完成实现对抗性众包

Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion

We determine statistical and computational limits for estimation of a
rank-one matrix (the spike) corrupted by an additive gaussian noise matrix, in
a sparse limit, where the underlying hidden vector (that constructs the
rank-one matrix) has a number of non-zero components that scales sub-linearly
with the total dimension of the vector, and the signal-to-noise ratio tends to
infinity at an appropriate speed. We prove explicit low-dimensional variational
formulas for the asymptotic mutual information between the spike and the
observed noisy matrix and analyze the approximate message passing algorithm in
the sparse regime. For Bernoulli and Bernoulli-Rademacher distributed vectors,
and when the sparsity and signal strength satisfy an appropriate scaling
relation, we find all-or-nothing phase transitions for the asymptotic minimum
and algorithmic mean-square errors. These jump from their maximum possible
value to zero, at well defined signal-to-noise thresholds whose asymptotic
values we determine exactly. In the asymptotic regime the
statistical-to-algorithmic gap diverges indicating that sparse recovery is hard
for approximate message passing.

本文研究在一个稀疏极限下，当底层隐藏向量（构建排名为一的矩阵）非零组成部分数与向量总维数的比例为亚线性，信噪比以适当的速度趋于无穷大时，估计被加性高斯噪声矩阵污染的排名为一的矩阵的统计和计算限制，并证明了渐近互信息的显式低维变分公式，分析了稀疏状态下的近似消息传递算法。对于伯努利和伯努利 - 拉德马赫分布向量，当稀疏度和信号强度满足适当的比例关系时，我们发现渐近最小和算法均方误差的全有或全无相变。在渐近情况下，统计与算法之间的差距发散，表明近似消息传递对于稀疏恢复是非常困难的。