Decentralized and Privacy-Preserving Low-Rank Matrix Completion
- PDF / 856,042 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 193 Views
Decentralized and Privacy-Preserving Low-Rank Matrix Completion An-Ya Lin1 · Qing Ling1
Received: 11 November 2014 / Revised: 6 February 2015 / Accepted: 6 February 2015 / Published online: 5 May 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press and Springer-Verlag Berlin Heidelberg 2015
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 , · · · , D L ] 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 , · · · , Y L ] 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. Keywords
Decentralized algorithm · Matrix completion · Privacy-preserving
Mathematics Subject Classification
49R99 · 90C90
1 Introduction Completing a low-rank (or approximately low-rank) matrix from an incomplete set of its entries has been a hot research topic in recent years [5,6,25]. This problemarises
B
Qing Ling [email protected] An-Ya Lin [email protected]
1
Department of Automation, University of Science and Technology of China, Hefei, China
123
190
A.-Y. Lin, Q. Ling
in various applications, such as collaborative filtering [1], system identification [19], internet traffic analysis [36], sensor localization [22], video processing [17], and phase retrieval [7], to name a few. This paper considers decentralized matrix completion, in which a network of agents collaborate to complete a low-rank matrix that is the collection of multiple local data matrices. To be specific, each agent observes some entries of its own local data matrix and exchanges information with its neighbors to complete the unobserved ones [18,21]. Particularly, we focus on designing a privacy-preserving decentralized matrix completion algorithm such that a malicious agent in the network is unable to recover local data matrices of other agents through neighboring information exchange. This privacy-preserving property is critical to protecting sensitive data that come from multiple sources (for example, medical data of hospitals, selling data of merchants), yet utilizing the data to jointly accomplish a matrix completion task. 1.1 Our
Data Loading...
