Abstract:

In this paper, we propose a decentralized algorithm to solve the low-rank matrix completion problem and analyze its privacy-preserving property. Suppose that we want to recover a low-rank matrix D = [D1,D2, · · · ,DL ] from a subset of its entries. In a network composed of L agents, each agent i observes some entries of Di . We factorize the unknown matrix D as the product of a public matrix X which is common to all agents and a private matrix Y = [Y1, Y2, · · · , YL ] of which Yi is held by agent i only. Each agent i updates Yi and its local estimate of X, denoted by X(i ), in an alternating manner. Through exchanging information with neighbors, all the agents move toward a consensus on the estimates X(i ). Once the consensus is (nearly) reached throughout the network, each agent i recovers Di = X(i )Yi , thus D is recovered. In this progress, communication through the network may disclose sensitive information about the data matrices Di to a malicious agent. We prove that in the proposed algorithm, D-LMaFit, if the network topology is well designed, the malicious agent is unable to reconstruct the sensitive information from others.

Key words: Decentralized algorithm ·, Matrix completion ·, Privacy-preserving