Homomorphic Matrix Completion
Authors: Xiao-Yang Liu
Zechu Li
Xiaodong Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Matrix completion
recommendation system
homomorphic encryption
differential privacy

Abstract: In recommendation systems, global positioning, system identification and mobile social networks, it is a fundamental routine that a server completes a low-rank matrix from an observed subset of its entries. However, sending data to a cloud server raises up the data privacy concern due to eavesdropping attacks and the single-point failure problem, e.g., the Netflix prize contest was canceled after a privacy lawsuit. In this paper, we propose a homomorphic matrix completion algorithm for privacy-preserving data completion. First, we formulate a \textit{homomorphic matrix completion} problem where a server performs matrix completion on cyphertexts, and propose an encryption scheme that is fast and easy to implement. Secondly, we prove that the proposed scheme satisfies the \textit{homomorphism property} that decrypting the recovered matrix on cyphertexts will obtain the target complete matrix in plaintext. Thirdly, we prove that the proposed scheme satisfies an $(\epsilon, \delta)$-differential privacy property. While with similar level of privacy guarantee, we reduce the best-known error bound $O(\sqrt[10]{n_1^3n_2})$ to EXACT recovery at a price of more samples. Finally, on numerical data and real-world data, we show that both homomorphic nuclear-norm minimization and alternating minimization algorithms achieve accurate recoveries on cyphertexts, verifying the homomorphism property.

Homomorphic Matrix Completion
Xiao- Yang Liu'r, Zechu Li Xiaodong Wang' Department Electrical Engineering, Columbia University, New York, Department of Computer Science, Columbia University, New York, (x12427, z12993, xw2008)@columbie. edu
Abstract
In recommendation systems, global positioning, system identification, and mobile social networks, is fundamental routine that server completes low-rank ma- trix from an observed subset of its entries. However, sending data to a cloud server raises up the data privacy concern due cavesdropping attacks and the single- point failure problem, e.g., the Netflix prize contest was canceled after a privacy lawsuit. In this paper, we propose a homomorphic matrix completion algorithm for crivacy-rresevvig purpose. First, we formulate a homomorphic matrix completion problem where a server performs matrix completion on cyphertexts, and propose encryption scheme that is fast and easy to implement. Secondly, we prove that the proposed scheme satisfies the homomorphism property that decrypting the re- covered matrix cyphertexts will obtain the target matrix (on plaintexts). Thirdly, we prove that the proposed scheme satisfies an (e, d)-differelttal privacy property. While with similar level of privacy guarantee,
reduce the best-known error bound O 'V m² EXACT recovery at price of more samples. Finally, synthetic data and real-world data, we show that both homomorphic nuclear-norn minimization and alternating minimization algorithms achieve accurate recoveries on cyphertexts, verifying the homomorphism property.
Introduction
The recurring low-rank matrix completion problem
KK
2
46 concerns completing
low-rank matrix from a randomly observed subset of entries. has wide applications in recommen-
dation systems (collaborative filtering) [|| 47 26), computer vision 2 H6 27 global positioning
48
32)
sensory data analysis in Internet of Things
2
34! 33
system identification. network data Existing works 1 g have demonstrated
analysis 51 I. mobile social networks
2 38
remarkable fact: if an n x matrix with rank < n satisfies a certain incoherence property, then with high probability, it is possible to exactly recover the matrix from O(nr poly log n) < n² entries using polynomial-tnn -ime algorithms. Intuitively, one needs roughly (2nr r²) parameters [6] (this the dimension of the tangent space to the manifold of rank-r matrices) fix rank r. and the sampling randomness introduces a log factor due to a coupon collector's 's effect. The information theoretical lower bound is Q(rr log n) [6] while the tightest known upper bound is O(nr log" n) g
matrix of
with another log n factor from the Golfing scheme used by the recovery algorithms.
The low-rank matrix completion problem usually deals with large-scale matrices that involve extensive computations, while in mobile computing, smart devices usually outsource such huge computation task to a cloud server. However, sending data to a server or publishing anonymized data raises up privacy concerns [23]
42], e.g., the recommendation contest Netflix prize canceled after 35 There are two major obstructive factors: anonymization in data publishing is
privacy lawsuit
still vulnerable, and storing sensitive data cloud server may encounter the single-point of failure
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Server: matrix completion
Server: homomorphic matrix completion
M g(M))
M, g
M,
M
May
M
M nz
M
M
M
Node 1
Node f22
Node
Node
(a) Plaintext
(b) Cyphertext
Figure 1: Matrix completion on plaintext VS. homomorphic matrix completion on cyphertext.
(SPOF) problem, say hackers. Existing works 20
99
10
address the privacy concern in various
ways, e.g., popular approach to add noise to the data 20
therefore making a tradeoff between
the recovery accuracy and the level of privacy.
In cloud computing and distributed systems, the homomorphism property [4] 45 allows computa- tions to be carried out on cyphertexts, generating an encrypted result which, when decrypted. matches the result of operations performed on the corresponding plaintexts. In this manner, homomorphic encryption securely chains together different services without sacrificing recovery accuracy, but may price of extensive computation. There are several partially homomorphic crypto-systema In addition, the homomorphic property can also be used create many other secure systems, for example secure voting systems, collision-resistantt hash functions, private information retrieval schemes
and also a number of fully homomorphic crypto-systems [4 45
4% etc.
In this paper, integrate the large-scale distributed matrix completion task with homomorphic eneryption-decryption scheme, which guarantees the EXACT recovery and differential privacy at price of more samples. First, we define the homomorphic matrix completion problem that ensures data privacy by preserving a homomorphism property between plaintexts and cyphertexts. Specifically, propose homomorphic encryption-decryptin scheme, in which each node performs local encryption and decryption, and uploads an encrypted incomplete vector to server that carries out the matrix completion computation. Then, we theoretically prove that the proposed scheme satisfies the homomorphism and differential privacy properties reducing the best-known error bound O( W/inn 20 to EXACT recovery. Finally, based on synthetic and real-world data, we show that the homomorphic nuclear-norm minimization and alternating minimization algorithms achieve accurate recoveries both eyphertexts and plaintexts, verifying the homomorphism property.
Homomorphic Matrix Completion Problem
First, we formally define the homomorphic matrix completion problem. Then, we introduce a notation of privacy by adapting the join (c, 8) differential privacy, which is subspace-aware variant.
2.1 Notations and Preliminaries
Notations: Let e; denote the i-th standard basis, I denote the x identity matrix, and I denote the identity linear operator. For matrix X, the (i. element is X,; X the j-th column is X,, and the transpose is X The concatenation of two matrices A E R=1 and B E R X with the same number of rows denoted by [A, B] E (na+)n)) By with high probability (w.h.p.) we mean that with probability least Cin c2 for some positive constants C1, Oz. Let (O, o²) denote a Gaussian distribution with mean 0 and standard deviation a. We use an overline to represent the encrypted version of variable: variables before encryption are called plaintexts, e.g., X. while the encrypted variables are called cyphertexts, e.g.. X.
Let Mp E RB1x denote the observed entries of data matrix M E XR2, where Ω S. ((1,1), (1,2), (21, indicates the observed entries. We define linear operator

---

Pa : R + m to represent the partial observation model as follows
(Pa(M)) = Mij, if (i.j)
(I)
O, otherwise.
Assuming the true data matrix M is low-rank, i.c., (M) = & min(n1, n2). The (compact) singular value decomposition (SVD) is M UEVT, where U R represents left singular vectors (a basis of the column subspace), V E R represents r right singular vectors (a basis of the row subspace), and = diag(( [1i, di. .or)) E IR" with singular values 0i 2 02 2 ... 2 Or 2 0. The f2-norm of vector is | l2, while the Frobenius norm and nuclear norm of M are ||M|| - / M and ||M]|- Ei= os, respectively. The operator norm (spectral norm)
of a matrix and a linear operator L are defined as follows
|M
sup
Ma = 01. and ||||| A sup |X||SSI
||((x)||r.
(2)
#ER" |
Definition 1. (Column subspace and null space (281) Let A Ru The set S(A) {b
I" Ax, x E R²*} is the column space or range of A, and the set Ker (A) = { E Ax 0} is the kernel or (right) null space of A.
The null space (kernel space) of operator Ps is Ker(Pn) = {Z R2=X""2 Pa
0}. which is denoted as Ω 1 Let Ω Uni(m) denote a set with m entries, which sampled uniformly from all sets of m entries, and f ~ Ber(p) denote set with E|s = m entries, where each entry is sampled independently according to a Bernoulli model with p = m/ m/(nin2).
Let Ptr and Py denote the orthogonal projections onto the column and row space of M, respectively,
Pu = Σ u.u = -U,, Pv = Σ D.aa AE(r]
VV..
(3)
tE(r)
Define an orthogonal decomposition RT X = T T where T is the linear space spanned by matrices with the same column space space M, and T' is its orthogonal complement that consists of matrices with row-space orthogonal to the row-space V and column-space orthogonal to the column-space U. T can be expressed follows
T T= (UA + BV T A B B BER
(4)
The orthogonal projection Pr onto T and the orthogonal projection onto T are as follows
(x) Xu XPy PuXPv, Pri (X) = - -I- (x) = (In, - Pu) - Pv).
(5)
2.2 Problem Formulation for Homomorphic Matrix Completion
We interested in completing large-scale matrices and want to outsource this compute-intensing task from mobile devices to a cloud server. Here we aim to preserve the matrix entries from leakage, which is the key concern for recommendation systems in Netflix's 's privacy lawsuit B51
Distributed matrix completion problem on plaintexts. Assume that there are n22 nodes with limited computing power and a cloud server with superior computing power. The j-th node has attribute vector M, E TR j = I..,, 02g however, it incomplete and the observed entries are indexed by set 22 {(,,)), (2,5), (n1,j)). We assume that the true values of these n2 vectors form low-rank matrix M E [gn with rank r & min(n n22,, the fornss of the attribute vectors is bounded by L, i.e., maxisisng |,,l 22222 I L, and the observation set l UJ=I...... Zz Nodes upload their incomplete vectors to a cloud server to carry out matrix completion task
Find a matrix X E R21x s.t. Pa(X) = Pa(M), rank( X) Sr,
(6)
where Ω ~ Uni(m) and r may be unknown. Without loss of generality, we assume that S n22 from now on. Note that our formulation also includes the case 3 where matrix is distributed into blocks and then is completed in parallel.
We adopt the notation - since Ker(Pa) corresponds to of matrices vanishing 2
3

---

Homomorphic matrix completion problem on cyphertexts. In cloud computing, the homomor- phism property allows computations to be carried out on eyphertexts, generating an encrypted result which, when decrypted, matches the result of operations performed on the plaintext. Following this paradigm, we define a homomorphic matrix completion problem that ensures data privacy. As shown in Fig. | this novel framework consists of three main steps:
1) each node locally encrypts as Pa. (M₂) Pa, (M(M)) with its private keys, = L,... R2, and uploads Pa, (M,) to cloud server that later forms an incomplete matrix Pa(M) E R x
2) the cloud server solves the following matrix completion problem given (a(MM and sends back the recovered vector M, to the j-th node, j = 1,.... 122.
Find a matrix E R x22, s.t. Pa(X)= - (M(M), rank X) S r;
where F rank(MM may be slightly bigger than r due to by the encryption scheme g()).
3) each node locally decrypts its own vector using private keys, i.c. M, = (M(M) 1,..., n22
2.3 Notions of Privacy
We introduce a new variant of differential privacy for low-rank matrices.
2.3.1 Differential Privacy
Let D .d.,..., 3 be a dataset of n entries and T be a fixed domain, where each entry dj E T encodes potentially sensitive information about node j. Let A T + O" be an algorithm that operates on dataset D and produces n outputs, one for each node j and from set of possible output O. Let D-j denote the dataset D without the entry of the j-th node, and similarly A-,(D) denote the set of outputs without the output for the j-th node. Let (dy; D-)) denote the dataset obtained by adding a data entry dj to the dataset D D
The (c, 8) differenntil privacy and joint (c, (),5) ddifferrrrll privacy 21 are given in the following. Definition 2. ((e, d)-fifeerettia privacy (22)). An algorithm A satisfies (e, (e, privacy if for any node j. any two possible values of data entry dy, d', E for node j. any tuple of data entries for all other nodes D-j E TT= and any output set O C O", we have
PA Pa(A(d;D--)) - D- D-)) [0]
(8)
Definition 3. (Joint (e, ddfffferretii privacy 1211). An algorithm A satisfies (e, j)-joint differential privacy if for any node j. any two possible values of data entry dj, d' E ET fTr node j. any tuple of data entries for all other nodes D-, E TT-1, and any output set O C O"-1, we have
PA[A- D) E 0 5 S PAlA,, D-2) E 0] 8 8.
Intuitively, an algorithm satisfies (e, diffferrenta privacy for any node j and dataset D. A(D) and D-y do not reveal "much" information about d,. For low-rank matrices, 20 used relaxed notion joint (c, (2.)) diiffereential privacy: an algorithm A satisfies joint (c, 8) dddfffeeret privacy if for any node j and dataset D, (D) (the output for the other n 1 nodes) and D-, (data entries of the other n - nodes) do not reveal "much" information about d,. Relaxing (c, 6) differrretii privacy to joint (c, -iffffereltaal privacy is reasonable for the matrix completion problem since the j-th column for the j-th node can reveal a lot of information about d,.
2.3.2 Differential Privacy for Low-rank Matrix Completion
We would like to point out that joint (e, 8) diifferentaa privacy in Def. 3 can be further refined. For a low-rank matrix M, its column subspace S(M) is global information, which is shared across all n2 nodes and can be easily inferred from A-, (D) and D-j. Note that the differential privacy notion aims to protect individual information, rather than global information. We adapt it to low-rank matrices by excluding the shared column subspace.
Low-rank matrices have linearly dependent columns, and this dependency reflected in the fact that they share a common column subspace. Formally, rank-r matrix M UEV can be expressed

---

Algorithm 1 Homomorphic matrix completion at the cloud server
Input: parameters 711, f22 r, k.
Output: matrix K E [ x
as public I: Generate a random matrix K E RT xE and broadcast K to all n2 nodes;
the recovered matrix X E I x (cyphertexts).
2: until received all f2 encrypted vectors Pa, (M,) (line 4 in Alg. 2 do
3: Carry out matrix completion task 4 and obtain X E 2
4: Send the recovered vector X, I back the j-th node, j 1,, .... 122.
5: end
Algorithm 2 Homomorphic matrix completion at node j. for 1,,,.. n1
Input: an incomplete vector Pn, (M,), observation set Qg, and parameters n2, k.
Output: an recovered vector X, (plaintexts).
1: until received K IR=x from the server (line in Alg. 1 do
2: Generate k random numbers R, Lid o2
3: Perform local eneryption as Pay (M₃) Pn, (M,) Pay (KR));
4: Upload Pn. (M,) to the cloud server;
5: end
6: until received the recovered vector X, from the cloud server (line 4 in Alg.
I do
7: Using R, and K, decrypt X, to obtain Xz, ie.. X, = X, K KRj-
8: end
as M = UC where U E x and C = EV E Brxx, alternatively, column can be expressed as M, = UC,, for j= = 1, ..., n2, where Cj is the coefficient vector (individual information) of the j-th node in the column subspace with basis U (global information).
The following subspace-aware joint (c, diffferentia privacy considers the coefficient vectors C, for j = 1, ...., i.e., D in Def. corresponds to the coefficient matrix C E R='=2
Definition 4. (Subspace-aware joint (c, d)d-fffereenti privacy). Assume 12 nodes' data vector form a rank-r matrix M E Rm xлz with M USV = UC where U Ra xr and = SV Brxma, A matrix completion algorithum A satisfies subspace-aware (c, j)-oint differential privacy if for any node j. any two possible coefficient vectors C, C'j E R' for node j. any tuple of coefficient vectors for all other nodes C-j E (rx(m==1), and any output set O C grxxa that consists of estimated coefficient vectors in a column subspace with basis U, we have
PAIA-,(C;C--JU)) S -PAlA, E +
(10)
3 Novel Homomorphie Framework for Matrix Completion
We propose homomorphic encryption-decryption scheme: node performs local encryption and decryption, and uploads an enerypted vector to server to perform the matrix completion computation.
3.1 Our Idea: Hiding Low-rank Data Matrix in Larger Subspace
To preserve the privacy of a low-rank data matrix M E R with rank r, our idea is to hide M (lies in an r-dimensional subspace) into a larger subspace of dimension F, such that F 2 r and r, r' < ny. A sound approach would be enlarging the original subspace of the data matrix (i.e., the plaintext) as follows: a cloud server generates random matrix K E R xk as public keys, k: < m1, and broadcasts K to all nodes; then, node generates k random numbers as private keys R, E TR and encrypts its vector M,- E TR as follows version with missing entries will be given in
M, = M, + KR,, j I..,, Equivalently, M = M + R..
(11)
In the eneryption scheme I1. M is added up with KRR, resulting in matrix M with rank 7 < r Since F < n,, M is also lowkrank. it is possible to recover M from subset of entries.
5

---

R1j x
K1
Known
Unknown
RRj x
Kk
Ma
Plaintext
Maj
Cyphertext
Figure 2: Our encryption method. Plaintext and eyphertext have the same set Q of missing entries.
3.2 Proposed Homomorphic Encryption-Decryytion Scheme
We propose homomorphic encryption-decryytion scheme that consists of the following steps, while the pseudocodes are summarzied in Alg. and Alg. 2
First, in line of Alg. the cloud server generates random matrix K E RR as public keys, then broadcasts to all n2 nodes.
Second, lines 1-5 of Alg. D after receiving K Rm from the server (line 1 Alg. D. the
j-th node locally carries out an encryption with & private keys (i.e., Rí E IR... As shown in Fig. the j-th node locally encrypts its incomplete vector Pay (M,) as follows
Pa, (M, Pa, (M,) Pny (KR;), j 1,..,
(12)
where RS Lid NO0, o IR), Pn, (K means keeping the entries in S2 and setting the entries in the complement set of 22 to be zeros, thus Pn, (M,) has the same set of missing entries as Pa, (M2). Note that R2 is stored locally, which are private keys that will NOT be shared with any other node. Then, each node uploads its encrypted vector Pny (M,) to the cloud server.
Third, lines 2-5 of Alg. [ after receiving all n2 encrypted vectors Ps, (M,). = l,..., 122 the server forms an incomplete matrix Mg with Ω = Uj=I..... Ωy. Then, the server carries matrix completion task in and sends the recovered vector X, back to the j-th node,
j 1,.... n22
Finally, in lines 11-13 of Alg. using the locally stored private keys Rj, and the public keys K, the j-th node decrypts its own vector, i.e., X, = -X- K KRj, I,... 12.
Homomorphism Property Holds at Price of More Samples
We prove that the homomorphism property holds for the proposed scheme, which guarantees exact recovery on cyphertexts at a cost of more samples. The detailed proofs are given in Appx. C
Starting from a necessary and sufficient condition in Lemmal) [ we relax to a sufficient condition in Lemma for the homomorphism property hold. Then, provide homomorphic version of Rudelson Selection Estimation Theorem in Theorem probability. Therefore, obtain sample complexity for EXACT recovery in Theorem where interesting finding is that the homomorphism property holds at price of more samples.
Overview:
2 that guarantees Lemma with high
4.1 Sufficient Condition for Low-rank Matrix Completion
We start from a necessary and sufficient condition for low-rank matrix completion. Note that similar necessary and sufficient condition for sparse vector recovery discussed in compressive sensing
46
Here, we apply a similar argument to obtain Lemma T
We define set of matrices with rank at most r and rank-descent cone follows
M (X e p rank(X) <r
(13)
(DM(M) (t(X M) E 12ix rank (X) Sr, f2 0),

---

where M is the closure of the manifold of rank-r matrices. Accordingly, for M, we have
M M (X e th x rran S S)
(14)
M) E 1
xx2 rank S 12.
Lemma 1. (Necessary and sufficient condition for low-rank matrix completion) M is the unique optimal solution O if and only i DM (MM
{0), where Ω denotes Ker(Pn).
Geometric interpretation: M is the unique optimal solution to problem (6) if and only if starting from M, the rank of M + increases for all directions D Ω where D is nonzero. Therefore, the homomorphism property of low-rank matrix completion in problem holds if
Ω- n (M {0) Ω n (M)
(15)
2 (Theorem 6.1)) Let M = UEV be the compact SVD of matrix M. The langent cone TM (M) of the set M at M is a linear subspace given by
Lemma 2. 1115
(M (UAT BV A B R2 -
(16)
and its complementary space is denoted by T-_
Since the rank-descent cone is a subset of the tangent cone defined in T6) Theorem 4.8). (M) C T, and DD (M) C T, we relax (15) to the following sufficient condition.
Lemma 3. A sufficient condition for the homomorphic property of matrix completion under the proposed scheme in Alg. and Alg. is n== (0).
Interpretation: i2 n nT = {0} holds, then we know that M- M + KR the unique optimal
solution to problem and M the unique optimal solution to problem 6 Since M M + KR a one-to-one mapping, a decryption scheme M KR will return the desired true matrix M.
4.2 Homomorphic Version of Rudelson Selection Estimation Theorem
The Rudelson selection estimation theorem 39
investigates the number of random points needed to bring a convex body into a nearly isotropic position. Such an approximate isometry property fundamentally useful to characterize the number of entries needed to complete a low-rank matrix.
Definition 5. (Coherence) Let U E R2x be the r left singular vectors of M (corresponds to the column subspace ((M)) and Pu be the orthogonal projection onto U. Then the coherence of U (or S(M), respectively) is defined as
M(S(M) = p(U) A
11
max IsiEn
P
n max IU Tell. Isisn
(17)
since (UTU)-1 and U is orthonormal.
The concept "coherence" measures the relationship between a low-dimensional space and the obser- vation operator Pg. namely the cosine (with scaling factor _) of the principal angle between the low-dimensional space and standard basis. M is said to satisfy the standard incoherence condition with parameter μi if
((U) S No: and (VV) S 14-
(18)
A small μo ensures that the information of the row/column spaces of M is not too concentrated on a small number of rows/columns. characterizes the contribution of an entry in recovering M: a small μo means that each entry provides approximated the same amount of information.
Theorem 1. (Rudelson selection estimation theorem R) Assume that Ω Ber(p) with = O Tnngg ), and M obeys the standard incoherence condition 18 with parameter pa- There
constant OR such that for
1, with probability 1133n 3n we have
Honer log 12)
1p PTPPPP -Prl S CR
<
(19)
m

---

We derive the following homomorphic variant of the Rudelson selection estimation theorem B9 and Our new contribution here to derive the conditions when the approximate isometry property will hold simultaneously for both cyphertexts and plaintexts.
will use guarantee Lemma 3.
Theorem (Homomorphic version of Rudelson selection estimation theorem) Assume that Ω ~ Ber(p) with p = O ((ing)) M and M satisfy the standard incoherence condition 18 with
parameter po and Mo. respectively. Under the proposed scheme in Alg. [and Alg. there are
constants Cr, CR such for 3 1, with probability
3nz -8 we have
T log 122)
(cyphertex() 110 PPPPP -Pll - V
< 1, which implies
m
(20)
- E < 1. nappor (9 log n2))
(plaintext) 11-1PypPAPT - Prll & CRV
m
Note that ||0- PPpPPP - -plll < implies that the sufficient condition 2 nT ====00
= holds.
4.3
Sample Complexity for EXACT Recovery
Then, we prove Theorem that the homormophism property holds for the proposed scheme in Alg, and Alg. provided that there are sufficient number of observations ([S2) large enough).
Theorem For Alg. and Alg. with probability 2 1 - -3n, the homomorphism property holds if
(10gF where Co a positive constant.
Next, we characterize the coherence change of Fo and provide the sample complexity for the EXACT recovery Alg. and Alg. 0
Lemma 4. The new coherence under the proposed scheme in Alg. and Alg. 2 satisfies
r Ho + C Cmax
logn2, 222 ) with probability 2 1 - c -3 log 122.
Po S
(21)
Combining Theorem 3 and Lemma
we characterize the required number of entries.
Corollary 1. For Alg. property holds if 2
and Alg. 2 with probabilit 2 - Grz enz log n2, the homomorphism
Colrag C max
max((k (o. (lg where c, Co, are positive constants.
Differential Privacy Property Holds
In this section, we show that the differential privacy holds for the proposed scheme in Alg. and Alg.
It is well-known that one can achieve (e, -ddiifferettial privacy by adding Gaussian noise.
Definition 6. (Privacy loss random variable (221 Considering mechanism A pair of databases D, D'D'. For an outcome o E O, the privacy loss on o is defined as the logarithmic ratio between the probability observe input D compared to that input D':
((A(DD) o)
C (0) A(D))IA(D") P(A(DD) = o)
(22)
where P(A(D) o) is probability density over a continuous set O.
Two potential issues of the proposed scheme in Alg. aad Alg. i the projection recovery and the rank value r may be unknown. Namely, for a single-round encryption case, one can do a corresponding projection to obtain the real data. Therefore, we execute the proposed scheme twice and introduce two parameters J1 and dz.
First-round encryption: the server randomly generats matrix K E IR and each node gener-
ates & random numbers R! iid \OO0, ofIx). Then, we have Pa M (P((M) + Pa(K R!). Second-round encryption: the server obtains the column space of M K2 E R with r= + 1 and then each node generates r k random numbers R3 iid
N(O, o Irte). Then we
have Pa (M) (a(M) (a(K3 RR).

---

observed entries (%)
NN
HNN
AM
HAM
90
75
60
45
30
15
1
15 30
45
75 90
15 30
45 60 rank
75
90
15 30
75 90 rank
60
15 30
45
75
90
rank
rank
Figure 3: Comparing NN and AM algorithms with their homomorphic versions. The figure plots the success rates within 10 trials, where the white and black cells mean "success" and "fail". The trial is "success" if RSE I 10-5 We set k 10 in Alg. and Alg.
Theorem 4 states that the proposed scheme satisfies the subspace-aware joint (e, d)-differential privacy in Section 2.3.2 The detailed proofs are given in Appx. D where the key is to quantify a under
which the random variable privacy loss in 22 is bounded by e, with probability at least 1 - 8.
Theorem 4. Let E E (0, 1) and e² > ln(1.25/0)) Assume the true data matrix M E R x has runk and each column has bounded kz-norm, i.e,, A maxisi5na ||1ll2 S L. Let R NO, I&) with 0ı 2 2cIn/21n(2) (n(2/8)/c and R.
~ NO, IbIr)) with 02 2 2mL2/22
then the encryption and decryption scheme in Alg. nand Alg. 2 satisfies the subspace-aware joint (e, diifferrrtiia privacy property.
substantial improvement is: for the level of privacy (the same parameters e, ô in the above joint (e. 6)-DP property), our algorithms are able to achieve EXACT recovery. Note that by proving the homomorphism property and characterising the sample complexity, we reduce the error bound O( / n2)2)) from 20 to ZERO since have EXACT recovery.
Performance Evaluation
We evaluate the proposed scheme synthetic data and real-world datasets using two matrix comple- tion algorithms 18 verifying the homomorphism property.
6.1 Experimental Settings
Datasets. We experiment with synthetic data and real-world datasets. The synthetic data is generated randomly according the low-rank 1, 1.0000 1, 000 matrix model and serves well-controlled inputs for verification. The real-world datasets include two benchmark datasets for recommendation systems, namely the MovieLens IOM (Top 400 3l and Netflix (Top 400) datasets. The MovieLenss dataset contains ratings of 400 most rated movies made by approximately 7, 0000 users, and the Netflix dataset contains ratings of 400 most rated movies made by approximately 480 thousand users.
Matrix completion algorithms. For the matrix completion on the server, we use nuclear-nome norm minimization (NN) and alternating minimization (AM) algorithms. In Section 6.2] we compare both algorithms with their homomorphic versions. In Section 6.3 on the real-world datasets, we also include the private Frank- (FW) algorithm 20 for comparison.
Performance metric. We measure the recovery error via the relative square root error RSE
1M-MIE. All experiments are executed for ten times and we report the average results. M
6.2 Results on Synthetic Data
We experiment with randomly generated low-rank matrices on NN and AM algorithms and their homomorphic versions HNN and HAM. We vary the rank r of the generated matrix and the percentage of observed entries from 1, 5, to 95. As shown Fig. 6.2 we observe two trends: for a certain rank r. the success rate increases as the percentage of observed entries increases; and 2) for certain percentage observed entries, the success rate decreases as the rank r increases. On the other hand, we find that the HNN and HAM need slightly more observed entries to reach the success threshold,
batps://movielenssorg

---

Movielens
Netflix
10
102
10a
10-3
10-2
RS
NN
RS
NN
10
10
10
10-6
AM
HAM
10-0
HAM
10
10 20 30 observed entries (%)
80 90
20 30 40 50 60 70 80 90 observed entries (%)
Figure 4: Results on MovieLensION IOM and Netflix datasets. We vary the percentage of observed entries and measure the RSE recovery error.
which verifies Theorem that the scheme guarantees exact recovery cost of more samples. As an interpretation, the homomorphic version is to hide the plaintext matrix into a larger space, namely from rank to rank + k. In this case, given that set 10 for the experiments, find that the results of HNN and HAM can obtained by shifting the results of their counterparts left one grid.
Results on MovieLens10% and Netflix Datasets
Fig. shows the results on MovieLens 10M and Nefii datasets. For the newly introduced compared algorithm FW, we set the privacy parameter e log((1/)) and = 10-6 For the NN and AM algorithms, the setting is the same in Section
First of all, we observe that the homomorphic algorithms can achieve significantly lower recovery errors than the eтror of FW algorithm. This points out the difference between the proposed scheme and existing strategies, which we do not sacrifice the recovery error improve the privacy. On the other hand, we find that the homomorphic algorithms can reach the same level of recovery error as the vanilla algorithms on plaintexts, but need more samples. Such a performance with our theoretical proof's and our observations in Section 6.2 Moreover, we analyze the impact of increasing the percentage of observed entries on three types algorithms, as shown in Fig. M For AM and FW algorithms, the recovery error decreases smoothly the percentage increases (note that the y-axis decreasing in log). However, the NN algorithm demonstrates significant error drop as we increase the percentage of observed entries.
consistent
7 Conclusion and Future Work
This work studied the problem of privacy-preservinn data completion in a distributed manner. To address the privacy concern, define the homomorphic matrix completion problem and propose a homomorphic encryption-deeryption scheme. Unlike existing works that preserve privacy by sacrificing recovery accuracy, our work guarantees the EXACT recovery while making tradeoff' between privacy and the number of samples. Then, we theoretically prove that the proposed scheme satisfies the homomorphism and differential privacy properties. Experimentally, we show that the proposed scheme is compatible with two matrix completion algorithms, namely the nuclear norm minimization and alternating minimization, and verify the homomorphism property.
In the future, it would be interesting to extend this homomophic framework to the tensor completion problem 31 32 It would also be practically interesting study federated learning application 24
and develop high-performant implementations for high-dimensional data analysis (50
36 50
Acknowledgement
Xiao- Xiao-Yang Liu would like thank Prof. John Wright (Department of Electrical Engineering at Columbia University) for his insightful sharing.
10

---

References
[1] Bennett and S. Lanning. The Neufli prize. Proceedings of KDD Cup and Workshop, volume 2007, page 35. New York, NY, USA, 2007.
[2] R. S. Cabral, F. Torre, J. P. Costeira, and A. Bernardino. Matrix completion for multi-label image classification. Advances in Neural Information Processing Systems, pages 190-198, 2011.
[3] E. J. Candès. Mathematics of sparsity (and few other things). In Proceedings of the Interna- tional Congress of Mathematicians, Seoul, South Korea, volume 123, 2014.
[4] E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9()):117, 2009.
[5] E. J. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489-509 2006.
[6] E.J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 5665):2033-2080 2010.
[7] T. P. Cason, P.-A. Absil, and P. Van Dooren. Iterative methods for low rank approximation of graph similarity matrices. Linear Algebra and its Applications, 438(4):1863 1188866312222 2013.
[8] V. Chandrasekaran, B. Recht, A. Parrilo, and A. S. Willsky. The convex geometry of linear inverse problems. Foundations of Computational Mathematics, 12(6):805-849, 2012.
[9] Y. Chen. Incoherence-optimall matrix completion. IEEE Transactions on Information Theory, 61(5):2909- -20009999222--22 2015.
[10] S. Chien, Jain, W. Krichene, Rendle, S. Song, A. Thakurta, and L. Zhang. Private alternating least squares: Practical private matrix completion with tighter rates. In International Conference on Machine Learning, pages 1877-1887. PMLR, 2021.
[11] L. Deng, H. Zheng, X.-Y. Liu, Feng, and 7. D. Chen. Network latency estimation with leverage sampling for personal devices: An adaptive tensor completion approach. IEEF/ACM Transactions on Networking, 286))2277722888, 2020.
[12] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends0 in Theoretical Computer Science, 933-4)211--077, 2014.
[13] A. Elmahdy, J. Ahn, C. Suh, and S. Mohajer. Matrix completion with hierarchical graph side information. Advances in Neural Information Processing Systems, 33:9061-9909 19774, 2020.
[14] C. Gentry. Fully homomorphic encryption using ideal lattices. ACM STOC, 9:169-178, 2009.
[15] Harris. Algebraic geometry: a firstt course, volume 133, Springer Science & Business Media, 2013.
[16] Dat T. Huynh and Ehsan Elhamifar. Interactive multi-label enn learning with partial labels. 2020 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pages 9420-9429, 2020.
[17] Jahn. Introduction to the theory of nonlinear optimization. Springer Science Business Media, 2007.
[18] P. Jain, P. Netrapalli, and S. Sanghavi. Low-rank matrix completion using alternating minimiza- tion. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665 (65-674,70 2013.
[19] P. Jain, J. Rush, A. Smith, S. Song, and A. Guha Thakurta. Differentially private model personalization. Advances in Neural Information Processing Systems, 34, 2021.
[20] Jain, O. D. Thakkar, and Thakurta. Differentially private matrix completion revisited. In International Conference Machine Learning, pages 2220-2229. 2018.

---

[21] M. Kearns, M. Pai, A. Roth, and J. Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the Conference on Innovations in Theoretical Computer Science, pages 403-410. ACM, 2014.
[22] R.H. Keshavan, A. Montanari, and S. Oh. Matrix completion from a few entries. IEEE Transactions on Information Theory, 56(6):2980-2999 29998, 2010.
[23] L. Kong, L. He, X.-Y. Liu, Y. Gu, M.-Y. Wu, and X. Liu. riiacy-preserving compressive sensing for crowdsensing based trajectory recovery. In IEEE 35th International Conference Distributed Computing Systems (ICDCS), pages 31-40, 2015.
[24] I.. Kong, X.-Y. Liu, H. Sheng, P. Zeng, and G. Chen. Federated tensor mining for secure industrial internet of things. IEEE Transactions on Industrial Informaties, 2019.
[25] I.. Kong, M. Xia, X.-Y. Liu, M.-Y. Wu, and X. Liu. Data loss and reconstruction in sensor networks. In Proceedings IEEE INFOCOM, pages 1654-1662. IEEE, 2013.
[26] Y. Koren, S. Rendle, and R. Bell. Advances in collaborative filtering. Recommender Systems Handbook, pages 91-142, 2022.
[27] Kaustav Kundu and Joseph Tighe. Exploiting weakly supervised visual patterns to learn from partial annotations. Advances in Neural Information Processing Systems, 33:561-572, 2020.
[28] A. J. Laub. Matrix analysis for scientists and engineers. Siam, 2005.
[29] Z. Li, B. Ding, C. Zhang, N. Li, and J. Zhou. Federated matrix factorization with privacy guarantee. Proceedings of the VLDB Endowment, 15(4):900-913, 2021.
[30] G. Liu, Q. Liu, and X. Yuan. A new theory for matrix completion. Advances in Neural Information Processing Systems, 30, 2017
[31] X.-Y. Liu, S. Aeron, V. Aggarwal, and X. Wang- Low-tubal-rank tensor completion using alternating minimization. IEEE Transactions on Information Theory, 66(3):1714-1737, 2019.
[32] X.-Y. Liu, S. Acron, V. Aggarwal, X. Wang, and M.-Y. Wu. Adaptive sampling of rf fingerprints for fine-grained indoor localization. IEEE Transactions on Mobile Computing, 15(10):2411- 2423, 2015.
[33] X.-Y. Liu and X. Wang. LS-decomposition for robust recovery of sensory big data. IEEE Transactions on Big Data, 4(4))542-555, 555, 2017.
[34] X.-Y. Liu, Y. Zhu, L. Kong, C. Liu, Y. Gu, A. V Vasilakos, and M.-Y. Wu. CDC: Compressive data collection for wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 26(8):2188-21) 2014.
[35] S. Lohr. Netflix cancels contest after concerns are raised about privacy. Web page: http://www nytimes wwtp:////////////ccaaaoll////aaa html 7mcubz The New Yorks Times, Mar. 12, 2010.
[36] H. Lu, T. Zhang, and X.-Y. Liu. High-performance homomorphic matrix completion gpus. In IEEE 21st International Conference on High Performance Computing and Communications, pages 1627-1634. IEEE, 2019.
[37] Lester W Mackey, Ameet Talwalkar, and Michael I Jordan. Distributed matrix completion and robust factorization, Journal of Machine Learning Research, 16(1):913-960, 2015.
[38] S. Rallapalli, L. Qiu, Y. Zhang, and Y.-C. Chen. Exploiting temporal stability and low-rank structure for localization mobile networks. Proceedings of the International Conference on Mobile Computing and Networking, pages 161-172 ACM, 2010.
[39] M. Rudelson. Random vectors in the isotropie position. Journal of Functional Analysis, 164(1):60-72, 1999.
12

---

[40] R. Schneider and A. Uschmajew. Convergence results for projected line- tearse methods on varieties of low-rank matrices via lojasiewicz inequality. SIAM Journal on Optimization. (5(1):622-646, 2015.
[41] S. Shalev-Shwartz, A. Gonen, and O. Shamir. Large-scale convex minimization with low-rank constraint. In International Conference on Machine Learning. 2011.
[42] V. Singhal and Steinke. Privately learning subspaces. Advances in Neural Information Processing Systems, 34, 2021.
[43] H. Sun and S.A. Jafar. The capacity of private information retrieval. IEEE Transactions on Information Theory, 2017.
[44] Jalaj Upadhyay. The price of privacy for low-rank factorization. Advances in Neural Information Processing Systems, 31, 2018.
[45] M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. Springer, Annual International Conference the Theory and Applications of Cryptographic Techniques, pages 24 43, 2010.
[46] J. Wright and Y. Ma. High- data analysis with low-dimensional models: Principles, compulation, and applications. Cambridge University Press, 2022.
[47] Q Wu, H. Zhang, X. Gao, J. Yan, and Zha. Towards open-world recommendation: An inductive model-basee collaborative filtering approach. In International Conference on Machine Learning, pages 11329 1339. PMLR, 2021.
[48] Q. Ye, J. Cheng, Du, X. Jia, and Zhang. matrix-coopllttonn approach mobile network localization. In Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pages 327-336. ACM, 2014.
[49] Zhang. X.-Y. Liu, X. Wang, and A. Walid, cuTensor- Tubal:: Efficient primitives for tubal-rank tensor lcarning operations gpus. IEEE Transactions Parallel and Distributed Systems, 3 31(3):595-616 610, 2019.
[50] T. Zhang, H. Lu, and X.-Y. Liu. High-performance homomorphic matrix completion on multiple gpus. IEEE Access, 8:25395-25406, 2020.
[51] Y. Zhang, M. Roughan, W. Willinger, and Qiu. Spatio-temporal compressive sensing and Internet traffic matrices. In ACM SIGCOMM Computer Communication Review, volume 39, pages 267-278. ACM, 2009.
13

---

Broader Impact Statement
This paper is within the area of private machine learning, which calls for completion by proposing homomorphic encryption- ceeypiiondderyptioon scheme. Due to the wide application areas of the matrix completion problem, this work may have broad practical impact recommendation systems, global positioning, system identification and mobile social networks, etc.
data
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Not aware of foresce negative impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yjvzL6L9Tv", "reviewer": "Reviewer_UWAB", "summary": "This paper studies the problem of privacy-preserving data completion in a distributed manner with the homomorphic matrix completion problem and propose a homomorphic encryption-decryption scheme. ", "questions": "(1) It is worth discussing whether the holomorphic matrix completion can work in that distributed setting.\n\n(2) One key assumption in matrix completion is low-rankness. However, the transformation M+KR in the server is determined by the public key K to guarantee low rankness. In practice, how do we choose the dimension k since we have no idea the true rank r of M?\n\n(3) The transformation g(M)=M+KR is too standard in DP. Is that possible to apply the non-linear transformation to improve privacy?\n\n(4) Could the authors numerically provide the privacy and recovery trade-off in different privacy levels?\n\n(5) Overall, this work follows a simple idea of differential privacy by replacing random noise as the product of public key and random noise. The guarantee of differential privacy and completion is relatively standard in existing works.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The targeted problem is interesting and important. This paper is well organized and easy to follow. Some theoretical results are provided to guarantee recovery and differential privacy.\n\nWeakness:\n(1) The centralized server framework in Figure 1(a) does not seem to be a well-known distributed framework in distributed matrix completion. There are too many nodes increasing with the dimension n2. In distributed matrix completion works, say, Mackey, Talwalkar, and Jordan (2015, JMLR), people distribute the matrix into blocks and complete them in parallel. It is worth discussing whether the holomorphic matrix completion can work in that distributed setting.\n\n(2) One key assumption in matrix completion is low-rankness. However, the transformation M+KR in the server is determined by the public key K to guarantee low rankness. In practice, how do we choose the dimension k since we have no idea the true rank r of M?\n\n(3) The transformation g(M)=M+KR is too standard in DP. Is that possible to apply the non-linear transformation to improve privacy?\n\n(4) Could the authors numerically provide the privacy and recovery trade-off in different privacy levels?\n\n(5) Overall, this work follows a simple idea of differential privacy by replacing random noise as the product of public key and random noise. The guarantee of differential privacy and completion is relatively standard in existing works.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b7y5nQsj1_", "reviewer": "Reviewer_WYT8", "summary": "The authors derive a novel homomorphic matrix completion algorithm with a proof that the homomorphism property holds provided certain technical conditions are satisfied, including a probabilistic bound on the number of observed entries required.\nThey also prove that the novel algorithm satisfies differential privacy constraints.\nThe authors' scheme solves the matrix completion problem on the server with homomorphically encrypted matrix entries while employing a higher rank constraint using any standard matrix completion method. The proof for the homomorphism property relies upon a homomorphic version of the Rudelson selection estimation theorem from [3].\n\nExperimental results on the Netflix and MovieLens datasets indicate that the homomorphic counterparts of nuclear norm (NN) minimization, dubbed HNN and alternating minimization (AM), dubbed HAM, are only slightly worse than the original ones and that the new schemes outperforms the differentially private Frank Wolf (FW) scheme.\n", "questions": "The parameter $k$ is a design parameter of the algorithm but the authors simply set it to $10$ in all experiments.\nShouldn't it vary with rank $r$ or $p$ ?\n", "limitations": "The limitations of the proposed method seems to be the trade-off between accuracy and privacy / number of samples, as discussed in the Conclusion. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The theoretical guarantees in the papers as summarized above appear to be quite strong.\n\n2. The experimental results as summarized above appear to be quite solid. The observation regarding the significant drop in error for HNN in Sec. 6.3 is also quite interesting.\n\n3. The authors provide geometric intuition for Lemma 1 regarding why $M$ is the exact solution to Eq (3) when a certain condition holds. It appears that Lemma 1 and this geometric interpretation is original and not already present in reference [3] or [6].\n\n4.\nHomomorphic encryption is generally supposed to be slow, but the proposed encryption / decryption method using public / private random matrices seems to be quite fast. \n\nWeaknesses\n\n1. This reviewer found the math in the paper hard to follow and hard to constantly refer to [3] or other references because the paper didn't seem to be self-contained.\nThe tangent cone mentioned after eq (12) is not defined in the paper and neither is the incoherence parameter used in (13).\n\n2. Both constants $C$ and $c$ are present in Lemma 3 and Corollary 1. It seems to this reviewer that $c = C$. \n\n3. The parameter $\\zeta$ in Theorem 4 doesn't seem to be defined anywhere.\n\n4. Typo: \"Rank-decent\" should be \"Rank-descent\" after eq (12).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IRj2ANJxif", "reviewer": "Reviewer_ux8W", "summary": "This paper presents a private and secure matrix completion scheme, where the data gets sent to a server for the task. The communication security is based on homomorphic encryption, and the privacy notion here is $(\\varepsilon,\\delta)$-differential privacy (DP). The authors work with a relaxed notion of joint DP.\n\nBoth theoretical and experimental results are provided for completeness. The focus is on exact recovery in this paper.\n\nEdit: Score updated.", "questions": "I don't necessarily have many questions. Could I know what the assumptions behind the data are? I would like to see what the sensitivity for the added noise is. How big is the norm bound $L$ in practice, and how is it affecting the accuracy of your scheme?\n\nWhat is the running time of the scheme compared to prior work?", "limitations": "I couldn't find where the authors discuss the limitations of their work. Could I be pointed to that, please?\n\nI feel that the writing quality could be improved by adding more detailed preliminaries for the main problem and the cryptographic primitives (even in the supplement).\n\nIn Equation 13, what is $\\mu(U)$?\n\nThere seems to be some typo at the end of Line 130.\n\nLines 114-115: What does $\\mathcal{A}-j(D)$ mean? How is this different from running $\\mathcal{A}$ on $D_{-j}$?\n\nLines 102-106: there are both bullets and numbering.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper does provide a scheme that seems to satisfy both the communication security and DP requirements. This paper actually focuses on exact recovery, as opposed to sacrificing accuracy in the prior work. The experimental results indicate compatibility with two matrix completion algorithms, NN and AM.\n\nWeaknesses:\n1. I wish the writing could be a bit more clear in terms of the cryptographic tools and the preliminaries related to matrix completion problem.\n2. The DP side of the scheme doesn't seem very interesting as it just involves adding some Gaussian noise. I don't see any assumptions about the data range (except that the $\\ell_2$ norm is bounded by $L$), or how they're being removed. I would have liked to see more of that. This problem might have just required something that simplistic, but I certainly wouldn't highlight its DP property as a huge selling-point for this reason.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept