Decentralized low-rank matrix completion

This paper introduces algorithms for the decentralized low-rank matrix completion problem. Assume a low-rank matrix W = [W₁,W₂, ...,W_L]. In a network, each agent ℓ observes some entries of W_ℓ. In order to recover the unobserved entries of W via decentralized computation, we factorize the unknown matrix W as the product of a public matrix X, common to all agents, and a private matrix Y = [Y₁,Y₂, ...,Y_L], where Y_ℓ is held by agent ℓ. Each agent ℓ alternatively updates Y_ℓ and its local estimate of X while communicating with its neighbors toward a consensus on the estimate. Once this consensus is (nearly) reached throughout the network, each agent ℓ recovers W_ℓ = XY_ℓ, and thus W is recovered. The communication cost is scalable to the number of agents, and W_ℓ and Y_ℓ are kept private to agent ℓ to a certain extent. The algorithm is accelerated by extrapolation and compares favorably to the centralized code in terms of recovery quality and robustness to rank over-estimate.