Low-rank matrix approximation is important in many applications for capturing the important aspects of data naturally described in a matrix form. In particular, we are interested in solving an inference problem using the leading singular vectors of a data matrix, which come from crowdsourcing platforms like Mechanical Turk. Crowdsourcing systems, in which numerous tasks are electronically distributed to numerous "information piece-workers", have emerged as an effective paradigm for human-powered solving of large scale problems. Because these low-paid workers can be unreliable, we need to devise schemes to infer the correct answers to these crowdsourcing tasks from possibly incorrect responses from the workers.
In this talk, to solve this inference problem, we introduce a new message-passing algorithm and prove that this algorithm is asymptotically optimal through comparison to an oracle that knows the reliability of every worker. This algorithm is inspired by the power iteration method for computing the leading singular vectors, and there is an interesting relation between the fixed point of the message-passing algorithm and the leading singular vector. The extrinsic nature of message-passing allows us prove sharp asymptotic bounds on the performance using density evolution. However, tracking the densities of real-valued messages is an a priori difficult task. We establish that the messages are sub-Gaussian using recursion, and compute
an upper bound on the parameters in a closed form.
Copyright. All Rights Reserved.