Low-rank Matrix Recovery with Unknown Correspondence
Authors: Zhiwei Tang
Tsung-Hui Chang
Xiaojing Ye
Hongyuan Zha
Venue: ICLR 2022 Submitted (2022)
Keywords: low-rank matrix recovery
optimal transport
min-max optimization
permutation matrix

Abstract: We study a matrix recovery problem with unknown correspondence: given the observation matrix $M_o=[A,\tilde P B]$, where $\tilde P$ is an unknown permutation matrix, we aim to recover the underlying matrix $M=[A,B]$. Such problem commonly arises in many applications where heterogeneous data are utilized and the correspondence among them are unknown, e.g., due to privacy concerns. We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. We propose an algorithm, $\text{M}^3\text{O}$ (Matrix recovery via Min-Max Optimization) which recasts this combinatorial problem as a continuous minimax optimization problem and solves it by proximal gradient with a Max-Oracle. $\text{M}^3\text{O}$ can also be applied to a more general scenario where we have missing entries in $M_o$ and multiple groups of data with distinct unknown correspondence. Experiments on  simulated data, the MovieLens 100K dataset and Yale B database show that $\text{M}^3\text{O}$ achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.

Under review as a conference paper at ICLR 2022
LOW-RANK MATRIX RECOVERY WITH UNKNOWN CORRESPONDENCE
Anonymous authors Paper under double-bling review
ABSTRACT
We study a matrix recovery problem with unknown correspondence: given the observation matrix M, [A, PB), where İ an unknown permutation matrix, aim to recover the underlying matrix M [A, B]. Such problem commonly arises in many applications where heterogeneous data are utilized and the corre- spondence among them are unknown, e-g., due to privacy concerns. We show that it is possible to recover M via solving nuclear norm minimization problem under proper low-rank condition the recovery of M. We propose an algorithm, M (Matrix recovery via Min-Max Optimization) which recasts this combinatorial problem as a continuous minimax optimization problem and solves it by proximal gradient with Max- -aa-le. M can also be applied to a more general scenario where we have missing entries M, and multiple groups of data with distinct unknown correspondence. Experi- ments on simulated data, the Moviel.ens 100K dataset and Yale database show that ' achieves state-of-the-as performance over several baselines and can cover the ground-truth correspondence with high accuracy.
M, with provable non-asymptotic error bound for
INTRODUCTION
In the era of big data, one usually needs to utilize data gathered from multiple disparate platforms when accomplishing a specific task. However, the correspondence among the data samples from these different sources are often unknown due to either missing identity information or privacy reasons (Unnukrıshann et all 2018 Gruteser et all 2003; Das & Lee, 20T8). Examples include the multi-image matching problem studied in (J1 et all 2014 Zeng et all 2012 Zhou et all 2013), the record linkage problem (Chan & Lofi, 2001) and the federated recommender system (Yang all 2020)
In the simplest scenario, we have two data matrices A = [a....., ag B = [b1, by] with aj E IT and b, R" which are from two different platforms (data sources). As discussed above, the correspondence (a,, b;) may not be available, and thereby the goal is to recover the underlying correspondence between aj,..., On and (a(1): ..., (M))) where #-)) denotes an unknown permutation. We can translate such problem described above as a matrix recovery problem, i.e., to
recover the matrix M = [A, B] from the permuted observation M, [A, PB). where / E Pn is an unknown permutation matrix and P,, denotes the set of n x a permutation matrices. We term this problem as Matrix Recovery with Unknown Correspondence (MRUC).
Inspired by the classical low-rank model for matrix recovery (Wright & Ma. 202T: Mazumder et all 2010: Haste et all 2015), we especially focus on the scenario where the matrix M features a certain low-rank structure. Such low-rank model has achieved great success in many applications like the recommender system (Schater el all 2IK); Mazumder et all, 201() and the image recovery and alignment problem (Zeng et all, 2012: Zhou all 2015). By denoting B, = PB, we want to solve the following rank minimization problem for MRUC, min PEP.
(1)
Practical applications. It is known that the recommender system often suffers from data sparsity (Zhang et all 20122 because users typically only provide ratings for very few items. To enlarge the set of observable ratings for each user, we may harness extra data from multiple platforms (Netflix, Amazon, Youtube, etc.). One classical work on this problem the multi-domain recommender system considered in (Zhang all 2012). Unfortunately, their work neglects crucial issue that

---

Under review as a conference paper at ICLR 2022
data from these diverse platforms (or domains) are not always well aligned for two primary reasons. The first is that the same user may use different identities, or even leave nothing about their identities, on these platforms. Another reason is that, those platforms are not allowed to share with each other the identity information about their users for preserving privacy. Another application is the visual permutation learning problem (Santa Cruz et all 2017), where one needs to recover the original image from the shuffled pixels. Both of the two applications give rise to a challenging extension of the MRUC problem, where we not only need recover multiple correspondence across different data sources, but also face the difficulty of dealing with the missing values in data matrix.
Relationship to the multivariate unlabeled sensing problem. Problem (II is closely related to the Multivariate Unlabeled Sensing (MUS) problem, which has been studied in (Pananjady et all 2017: Zhang et al, 2019:::: Zhang & Li MIZI; Slawski et all (illaa)) Specifically, the MUS is the multivariate linear regression problem with unknown correspondence, i.c., it solves
[|Y PXW]] |/:
min
PEP,, WE, ER
where W E m22xxm is the regression coefficient matrix, Y E R=xm and X E Raxma denotes the output and the permuted input respectively, and II-II is the matrix Frobenius norm. In fact, concurrent work (Yao et all (02I)) studies the same rank minimization problem as (W), but their approach is to solve it using the algorithm developed for MUS problem. Despite of the similarity to the MUS problem, we remark that MRUC problem has it own distinct features and, as shown in Section EI the algorithm for the MUS algorithm can not be directly and effectively applied, especially when there are multiple unknown correspondence and missing entries to be considered.
Related works. To the best of our knowledge, the concurrent and independent (Yao el all. 2021) is the only work that also considers the MRUC problem. Theoretically, (Yao 2021I showed that there exists non-empty open subset U C Te [== such that VM E U, solving (I) is bound to recover the original correspondence. However, such results only prove its existence for the subset U and do not provide a concrete characterization. Regarding the algorithm design, (Yaa (02T) follows the idea of (Slawski et all, 20206xa and treats problem (ID) heuristically as a MUS problem. However, there are two main drawbacks in their algorithm that largely limit its practical value. First, in the dense permutation scenario, it ignores the interaction among the shuffled columns and hence can not utilize the prior knowledge on the unknown permutation to have an improved performance; Second, their method can not deal with data with missing values.
Contributions of this work. Our contributions in this work lie in both theoretical and practical aspects. Theoretically, we are the first to rigorously study how the rank of the data matrix is per- turbed by the permutation, and show that problem (II) can be used to recover generic low-rank random matrix almost surely. Besides, we also propose a nuclear norm minimization problem as surrogate for problem (II) The most important theoretical result in this work is that we provide a non-as -on-asymptotic analysis to bound the error of the nuclear norm minimization problem under a mild assumption. Practically, we propose an efficient algorithm 'O that solves the nuclear norm minimization problem, which overcomes the aforementioned two shortcomings in (Yao et all, (021I). Notably, M²O works very well even for an extremely difficult task, where we need to recover mul- tiple unknown correspondence from the data that are densely permuted and contain missing values. We remark that this is so far a challenging problem unexplored in the existing literature.
Outline. For conciseness, we will first study the MRUC problem with single unknown correspon- dence, and then show that the theoretical results and the algorithm can be readily extended to the more complicated scenarios. We start with building the theoretical results for (II) and its convex relaxation in Section 2 Then, the algorithm is developed in Section EL The simulation results presented in Section A and the conclusions are drawn in Section E.
Notations, Given two matrices X, Y E R we denote (X, = ΣT_ E}=1 XiyY as the matrix inner product. We denote X()) the ith row of the matrix X and ((i, as the element at the ith row and the jth column. We denote 1mm E R and 1axm E R= as the all-one vector and matrix, respectively, and I,, be the n X n identity matrix. For E RT, 8 E RR, we define the operator @ as a + 3 = al1, + 1 E R We denote || I|= as the nuclear norm for matrices. For vectors, denote ||- 1lo. || |/1 as the zero norm and 1-norm respectively.
2 MATRIX RECOVERY VIA A LOW-RANK MODEL
How is the matrix rank perturbed by the row permutation? To answer this fundamental question, first introduce the cycle decomposition of a permutation.
2

---

Under review as a conference paper at ICLR 2022
Definition 1 (Cycle decomposition of a permutation (Dummit & Foote, 1991)). Let S be a finite
set and π (.) be a permutation on S. A cycle (01,..., an) is a permutation sending ag to as+1 for 1 1 S n 1 and a, to d1 Then cycle decomposition of iT)) is an expression of (-) union several disjoint eycles".
It can be verified that any permutation on finite set has a unique cycle decomposition (Dummit& & Footd, (191)). Therefore, we can define the cycle number of a permutation T(-) as the number of disjoint cycles with length greater than 1, which denoted as C(T). We also define the non-sparsity of a permutation as the Hamming distance between it and the original sequence, i.e., (TT) E.es [[](s) & s). It is obvious that H (ΛT) > C(T)) if is not an identity permutation. As a simple example, we consider the permutation (-) that maps the sequence (1,2.3.4,5,6) to (3.1.2.5.4.6). Now the cycle decomposition for it is x() = (132) (45) (5), and ((T) = 2, (T) = 5.
In all the following theoretical results, we denote the original matrix as . = [A, BJ Rax with A E Raxmaa, , B E R=xms, and rank(M) = r, rank(A) = rA, rank = TB. We denote the corresponding permutation as p-) for any permutation matrix P E P... The following proposition says that the perturbation effect of a permutation π on the rank of M becomes stronger, if т permutes more rows and contains less cycles. Proposition 1. VP E Pn.. we have rank([A, PB)) S min m, + + (((T)))C(<T)))
(3) We have similar result for the case with multiple permutations, which is summarized in Corollary II] in Appendix A. It turns out that, without any assumption on M, (C) is the tightest upper bound for the rank of perturbed matrix. Notably, the following proposition says that the upper bound in (G) is attained with probability 1 for generic low-rank random matrix.
Definition 2. A probability distribution on R is called proper distribution if its density function p(-) is absolutely continuous with respect the Lebesgue measure on R.
Proposition 2. If the original matrix M is random matrix with M RE where R E Rxx and E E Rm are two random matrices whose entries are i.i.d and follow a proper distribution on R, and r < min / / m., m.), then vP E Pn,, the equality rank([A, PB]) = min ((Tp) C(TP)}
xm
holds with probability I.
Convex relaxation for the rank function. Despite the previous theoretical justification for problem (1) it is non-convex and non-smooth. Another crucial issue is that we often have noisy observation matrix and it is well known that the rank function is extremely sensitive to the additive noise. In this paper, we assume that the observation matrix is corrupted by i.i.d Gaussian additive noise, i.c.,
Mo- = [A,, B,] = [A, PB] + W, where W (i.j) ~ (O, o²),
where 2 reflects the strength of the noise. We first denote the singular values of a matrix X E >2
as x:: "..... x where k = min m) Since rank(X)) = Il x: ..... x Illu. from Proposition 2 we can view the perturbation effect of a permutation to a low-rank matrix as breaking the sparsity of its singular values. This view leads naturally to the well-known 1-norm minimization problem which has been proven robust to additive noise and can yield sparse solution (Wright & Ma, 1022)), i.e.,
min [[[A,, PB.lI. = [loo,r...., ..., o.l111
(5)
PEP
Since for arbitrary matrix, the 1-norm of its singular values is equivalent to its nuclear norm, refer problem (5) as the nuclear norm minimization problem.
Theoretical justification for the nuclear norm. Nuclear norm has long history used as a convex surrogate for the rank, and it has been theoretically justified for applications like low-rank matrix completion (Candes & Tao, 2010: Wright & Ma. 2020).. is also important to see whether the nuclear norm is still good surrogate for the rank minimization problem (I). In this work, we establish a sufficient condition on A and B under which problem (5) is provably justified for corre- spondence recovery. We denote A = Eee o' B B= Em "B" as the singular values decomposition of A and B, where the o'A and d'B are the non-zero singular values.
Firstly, from the definition of nuclear norm, it can be simply verified for any P P P., that
-2/N~ < (IIA,, PB]I [|M || S Z/N,
(6)
where we denote N = max [B[].] and Z = [ain||AAl, 1.). The inequality (k) indicates that A and B should have comparable magnitude, i.e., |||]]. = [| otherwise the influence the permutation will be less significant. Therefore, we are interested in the scenario where the singular values of A and B are comparable, which is described as the following Assumption II.
Two cycles are disjoint if they do not have common elements
3

---

Under review as a conference paper at ICLR 2022
Assumption 1. There exists constant 61 2 0 such that
J - - S E1, = 1,.,7
where we denote that o = 0 rAs and d 0 ifi rn.
Similar to the matrix rank, we also need a proper low-rank assumption on the matrix M for the nuclear norm. In this work, particularly study the scenario that the left singular vectors of A and B are similar, which we formally describe as Assumption Q We refer Assumption 0 as a proper low-rank assumption, because it indicates that the column space of M can be approximated by the column space of one of its submatrices.
Assumption 2. There exists constant 2 0 such that
Ilu' uللl S E2, Vi TT
where we denote T min min((rA.B)
Furthermore, we also need that all the column singular vectors "'..... u WB..... ... u are variant under any P Pn with * In: we define vector u R be variant under a P E Pa Pu * u. One simple and weak condition for a vector to satisfy such property is that dose not contains duplicated elements, which leads to the following Assumption R
Assumption 3. There exists a constant Eg 2 such that
min min (u(1) u(j) 2 es 0, NEU #ø
where U = {u u. B B).
In summary. the assumptions mentioned above feature typical low-rank structure in M, and implies that the nuclear norm of M is sensitive to permutation. With the three assumptions, we have following important theorem, which provides high probability bound for the approximation error of (5))
We denote the solution (5)) p* and let and स be the corresponding permutation to the per- mutation matrices p=T and P. respectively. We define the difference between the permutations n and गे as the Hamming distance
du (T #)
Σ I(= #1))
Theorem 1, Under Assumptions 7 and R. if additionally 61 S M o S
dr <2 S min
/2M 2N
and
2/2T
M 1612, then the following bound for the Hamming distance
2
2 2 3
V2D
du( <
2 D (V2 2)er
(
VTea
(10)
22 2/2DTo
holds with probability at least
2 expl
D where L = max(ni m). = |||||+ + |||| 8L
The proof to all the aforementioned theoretical results are provided in Appendix A
see that when e3 0, and e - 0, 62 - error d (x*, f) will converge to zero with probability 1. Furthermore, we can also discover that the correspondence can be difficult recover when:
Remark 1. From Theorem
0, the
The rank original matrix M is high, which can seen from (IU)
The magnitude of A and B w.r.t rank or nuclear norm not comparable, which can be from ( and (
The strength of noise is high, which can be seen from (III) and the probability in Theorem ||
Notably, the numerical experiments Section corroborate our claims as well.
4

---

Under review as a conference paper at ICLR 2022
Remark 2. Additionally, from the proof of Theorem MI we find that the fundamental reason for the success of (55) is that M satisfies the previous assumptions, have
1.10
20%
1.08
40%
60%
1.06
80%
[[[A, PB]II+/|MMI
O ((1 (1)))
(11)
LA Pad
1.04
In many applications, we can only observe part of the full data. Therefore, it is also worthwhile to investigate whether (III) still holds when we can only access a small subset of the entries in M.. Notably, Figure M gives the positive answer and shows that the relationship (LII) is gracefully degraded when the percentage of observable entries decreasing. This phenomenon remarkable since it indicates the original correspondence can be recovered from only part of the full data. The matrices used to generate Figure are the same as those in Section I.l. and the nuclear norm is computed approximately by first filling the missing entries using Soft-Impute algorithm (Mazumder etal, 2010).
1.00
1.00
20
40
60
80
100
H(pt))
Figure I: The relationship ([ un- der different percentages of observ- able entries.
3 ALGORITHM
In this section, consider the scenario with missing values, i.e., our observed data is Pn(MM) Pal[AA: B.]), where Pn is an operator that selects entries that are in the set of observable indices Q. In this scenario, problem (E) can not be directly used since the evaluation of the nuclear norm and optimization of the permutation are coupled together. Inspired by the matrix completion method (Hastie all 2015; Mazumder all 20IM), we propose to solve an alternative form of (5) as follows,
min min PallA,, PBo)) - Pa( + MER PEP..
(12)
where À > is the penalty coefficient. We denote that M [M MR] and MA, MB are the two submatrices with the same dimension as Ao and B, respectively. We can write (12) equivalently as
(a((A) - Pa(M || + (C((M)), + M
min min ERR PEP,
(13)
where C(MB) R is the pairing cost matrix with
((MB)(i,))= = Σ (Mali.""- -o(i,")))) Vi,j I,..,,
(r")ER
Baseline algorithm. A conventional strategy to handle optimization problem like (3) is the alternating minimization or the block coordinate descent algorithm (Abid 2017). Specifically, it executes the following two updates iteratively until it converges.
new +
arg min Pao([A.. Pold B.l) - Pa(TT) + + |M |
(14)
MERaxm
pnew arg min (C(MB"", P). PEP.
(15)
The first update step (44) is a convex optimization problem and can be solved by the proximal gradient algorithm (Mazumder et al, 20I0). The second update step (IS) is actually discrete optimal transport problem which can be solved by the classical Hungarian algorithm with time complexity O(n²) (Jonker & Volgenant, (886) However, as will see in the Section EL this algorithm performs poorly, and it is likely to fall into an undesirable local solution quickly in practice. Specifically, the main reason is that the solution of (ILS) is often not unique and small change in MB would lead to large change of P. To address this issue, we propose a novel and efficient algorithm O' algorithm based the entropic optimal transport (Peyré et all 2019) and min-max optimization (Uin et all, 2020).
Smoothing the permutation with entropy regularization. For any a E R b E R", we define II(a, b) {S m=xm SS,, a, S 1,, b, S(i.j) 2 0, Vi.j),
which is also known as the Birkhoff polytope. The famous Birkhoff-von Neumann theorem (Birkhoff, 1946) states that the set of extremal points of IT(1,, I,,) equal to P,,- Inspired by (Xie all 20221) and the interior point method for linear programming (Berisckas (997), in order to smooth the optimization process of the bascline algorithm, we relax P from being an exact per- mutation matrix, i.e., to keep P staying inside the Birkhoff polytope I[(1,, 1,). That is, propose to replace the combinatorial problem (LS) with the following continuous optimization problem
min (C(MB), P\ + (P),
(16)
PeIl(1..1.))
5

---

Under review as a conference paper at ICLR 2022
where H(P) def. Σ,g P(o,)) - -1) is the matrix negative entropy and > is the regularization coefficient. Notably. (L)) also known as the Entropic Optimal Transport (EOT) problem. According to (Peyré et all 2019) (IT) is a strongly convex optimization problem with respect to I-norm and can be solved roughly in the (n²²) complexity per iteration by the Sinkhorn algorithm. Specifically, the Sinkhorn algorithm solves the dual problem of (IIG).
max We (MM,B, 0) def. (1n, ax) + (In: (3 -e( ( (nnxn exp a.SEI
+ 3 - C(MB)
(17)
6
which reduces the variables dimension from n² to 2n and is thus greatly favorable in the high dimension scenario. By substituting the inner minimization problem of (LS) with (IT), we end up with solving the following unconstrained min-max optimization problem
A Mall W.MM a, ()+ A M
min max M 0,8
(18)
Follows the idea of (ln et all 2020), we consider to adopt proximal gradient algorithm with a Max-Oracle for (II). Specifically, we employ the Skinhorn algorithm (Peyré et all 2019) as the Max- Oracle to retrieve an E-good solution of the inner max problem (I We summarize our proposed algorithm O (Matrix recovery via Min-Max Optimization) in Algorithm II where XJoXI|-11. (+) is the proximal operator of nuclear norm and Pk is the gradient stepsize. The convergence property of O can be obtained by following @ all 2020), which shows that, with a decaying stepsize, O is bound to converge an E-good Nash equilibrium within O iterations.
Algorithm 1: M
while not converged do For the tolerance e, run the Sinkhorn algorithm to find a", f such that
W.(M ai ,8) max a,
W. (M a, 3) - E;
Perform M++ + Xrox Xl Il, (M* Ph V M
F. (M a ())), where
F, a, 3) def. A MA | + W. W.MMB,,, a);
end
Remark 3. A recent work (Kie et all 202() proposes a decaying strategy for the entropy regular- ization coefficient in (IT) so that the optimal solutions of (IIS) and (IG)) do not deviate too much. Inspired by it, in our practice, we take large e the beginning and gradually shrink by half until the objective function stops improving for K steps.
Remark 4. A useful trick is that we should not take large stepsize Pk in the early iterations because the permutation matrix could still be far away from the optimal one. However, small stepsize would lead to slow convergence. Heuristically, we propose an adaptive stepsize strategy that performs well in practice. For the solution of (IG) Pk: at the kth iteration, we compute the two statistics
6z = Pk-1 Pp /2n and cs = max, (a())) 1n /n.
Here òR represents how fast the permutation matrix Ps. changes over the iterations, while ck measures how far the current Pr. is close to an exact permutation matrix. Both òg and Ce re- flect the confidence
the current found correspondence. Based them, we the stepsize as where w > is tunable parameter which is often set to value between
Pk+1 = (1-6x) (1 0.5 3. w actually trades off the convergence speed and final performance. The smaller the w, the faster the convergence. Therefore, practical way is to start with a small w, and gradually increase it until the final performance stops improving.
Remark 5. As discussed in Section II in many cases we have to deal with the problem that in- volves multiple correspondence, i.c., we need to recover the matrix M = [A, Bi.... Ba] from the observation data (M),),, where
M. [Ao,
[A, [.A PaBa + W.
where P E Pn and W is a noise matrix. We refer such problem as the d-correspondence problem. An important observation is that, although the number of possible correspondence increase expo- nentially as d grows, the complexity O per iteration only linearly increases with d and can be implemented in a fully parallel fashion. Specifically, in this scenario, we solve the problem

---

Under review as a conference paper at ICLR 2022
(Po(A)) - Pr((MA) 2 +
(C(M)) + =e((P)) + |M
min min M Pa.....P
(19)
s.t. P. E IT, 1n), 1= 1=-....,d
where we denote M = aM MB, MB.l. Here MA and MB, have the same dimension with A and B% respectively. One can find that the inner problems for solving Pt are actually decoupled for each I, which guarantees an efficient parallel implementation.
Remark 6. Since x problem (l22) has similar form to that considered in (Mazumder et all 2010)
We adopt the same tuning strategy of X as in (Mazumder 2010), which suggests that we should start with large Ả and gradually decrease it. We relegate more details about O' to Appendix A
4 EXPERIMENTS
In this section, evaluate our proposed O0 on both synthetic and real-world datasets, including the Moviel.nns 100K and the Extended Yale B dataset. We also provide an ablation study for the decaying entropy regularization strategy and the adaptive stepsize strategy pro- posed in Remarks 3 and 4. In all the ex- periments, we employ the Soft-Impute algorithm (Mazumder all 2010) as standard algorithm for matrix completion. Extra experiment details and auxiliary results can be found in Appendix A
A/GHS
Buss Orudi
1020
2500
2000
2500
(a) Objective value
(b) Permutation error
Figure 2: Performance of various algorithms on simulated 1- correspondence problem.
Algorithms. We denote the following algorithms for comparison in all the experiments:
1. Oracle: Running the Soft-Impute algorithm with ground-truth correspondence.
2. Baseline: The Baseline algorithm in (I4) and (IS))
3. MUS: Since there is currently no existing algorithm directly applicable to the scenario consid- ered by (T9), inspired by (Yao et all, 2021), we modify and extend the algorithm in (Zhang & Li, 202(), which is originally proposed for the MUS problem, to deal with the MRUC problem.
The details of the adapted algorithm are provided in Appendix A.S.
4.1 SYNTHETIC DATA
We first investigate the property of our proposed O algorithm on the synthetic data.
Data generation. We generate the original data matrix in this form M RE + n,W, where R E Raxr, E E R='xm, W E R=xm and rj > O indicates the strength of the additive noise. The entries of R, E, W are all i.id sampled from the (O, 1). Then we split the data matrix M by M = [A, B ...... Ba] where we denote A E REXmA, B, E Rnxm1 .... B, E Raxma to represent data from d ++ 1 data sources. The permuted observation matrix M, is obtained by first generating d permutation matrices Pi. Pa randomly and independently, and then computing M, = [A, Pt Bi, PaBa]. Finally, we remove (1 - [ 100% (n m)) percent of the entries of M, randomly and uniformly, where [Ω2 indicating the number of observable entries.
Ablation study. We denote the following variants of MDO for the ablation study.
1. Ma O-AS-DE: OoO with both Adpative Stepsize and Decaying Entropy regularization.
2. M O-DE: &o with Decaying Entropy regularization only. M and M adopt constant stepsize Pk = 0.5 and Pk = 0.01, respectively.
3. M O-A:: OoO with Adpative Stepsize only. The entropy coefficient is fixed to 0.0005.
In the following results, we denote मi as the corresponding permutation to Pt. We initialize M from Gaussian distribution for the M²O algorithm and its variants. We choose initial as 0.1 and K = 100 as the default for the decaying entropy regularization, and set w = as the default for the adaptive stepsize. We also report the achieved objective values of (IT) for the tested algorithms, except for the MUS algorithm since has a different objective. We denote â as the recovered permutation.
Results. Figure X displays the result under the setting 7 0.1, [2] 100% m) = 80%, n = m = 100, r = 5, d 1, mA = 60 and m, = 40. The algorithm M'O-AS-DE achieves the best result, and can recover the ground-truth correspondence. M. behaves similarly Baseline
7

---

Under review as a conference paper at ICLR 2022
and MUS. They all converge to poor local solution quickly. M converges quickly and also falls into a poor local solution due to large stepsize, while M adopts a small stepsize and hence suffers from slow convergence. Due to the superiority of O over the other variants, in the following results, we refer M$O as M-O-AS-DE for short.
1-correspondence problem under different regimes w.r.t [S], v, r and mA/n. n. Here we use ma/n to control the difference of the magnitude of the submatrices, As we can see, the results are well aligned with our prediction Remarks and 2.
Figure B examine M
Finally, we examine O on a few d-correspondence problems. See Table M for various results, where we set r and = 0.1. Notice that for the 4-correspondence problem in the table, there are (100t)² possible correspondence. Even for such difficult problem, Mc is able to recover 61 61.5% of the ground-truth correspondence with a good initialization.
180
100
100
8 8
60
56. mL.
70
20
DO
100
0.1
0.
0.3
0.4
0.
30
15
20
25
03
63
25
07
09
(a) dæ V.S. [25
(b) du v.s.
(c) dæ V.S.
(d) du v.s. ma/n
Figure 3: Performance of M 1-correspondence problem under different levels of [92], T, and ma/n The default setting is [S2] 100%/(n m)) 80%. 7) = 0.1, n m 100, r 5, mA 60, and m. 40. The mean with minimum and maximum are calculated from different random initializations.
Table I:
Performance of OO for various d-correspondence problems. The normalized permutation error Ei (ft, mi)dd reported meantstt (min) over 10 different random initializations.
(n, mA, M11, ms)
d
[|]]
100% (n m)
Σ Σi= (f Rt)/d
(100,40,30.30)
2
40%
33.35 1: 32.85 (0.00)
(100,20,40.40)
40%
58.90 1: 27.21 (2.00)
(100,45,25.255255,
3
50%
61.97 1 15.41 (37.33)
1100,40,,5,22,25222
4
60%
59.90 = 13.64 (38.50)
4.2 MULTI-DOMAIN RECOMMENDER SYSTEM WITHOUT CORRESPONDENCE
In this section, we study the performance of Oo real world dataset Moviel 100K which a widely used movie recommendation dataset (Harper & Konstan, 2015). In this application, we mainly focus on the metric Root Mean Squared Error (RMSE), i.c.,
RMSE def.
Σ May M,,)
Data. MovieLens 100K contains 100,000 ratings within the scale 1-5. The ratings are given by 943 users on 1,682 movies. Genre information about movies is also provided. We adopt a similar setting with (Khang et all, 2012). We extract five most popular genres, which are Comedy, Romance, Drama, Action, Thriller respectively, to define the data from different domains (or platforms). In addition to (Zhang et all 2012), we randomly permute the indexes of the users from these five domains respectively, so that the correspondence among these data become unknown. In this way, the problem belongs to the 4-correspondence problem discussed before. The ratings are split randomly, with 80% of them as the training data and the other 20% of them as the test data.
Algorithms. We consider the following additional algorithms for comparison.
1. SIC: Running the Soft-Impute algorithm independently for the 5 different platforms.
2. SIR: Running the Soft- Soft-Impute algorithm with Randomly generated correspondence. Results. As discussed in experiments on the simulated data, the exact recovery of correspondence becomes impossible due to the small amount of observable entries. Therefore, in the following experiment, since exact correspondence is not needed, we fix 0.05 for M Table E shows the results by averaging the RMSE on the test data over 10 different random seeds.
We can first see that the matrix completion with a wrong correspondence, i.e., SIR, can be harm- ful to the overall performance since it even worse than the results of SIC. Notably, although the ground-truth correspondence not be recovered, each platform can still benefit from MC since it
8

---

Under review as a conference paper at ICLR 2022
improves the performance over SIC. This is mainly because O is still able to correspond similar users for inferring missing ratings. On the contrary, since both Baseline and MUS can only establish an exact one-to-one correspondence for each user, they fail to improve SIC significantly. Remark- ably, ' is only inferior to the Oracle method a little, and even achieves lower test RMSE than the Oracle method on the Comedy genre.
Table 2: Test RMSE of various algorithms on Movielens 100K
Method
Comedy
Romance
Drama
Action
Thriller
Total
SIR 1,0202
1.0188
0.9808
0,9803
0.9811
0.9944
SIC
0.9694
0.9695
0.9317
0.9175
0,9253
0,9418
MUS
0,9659
0.9842
0,9423
0,9305
0,9306
0,9485
Baseline
0.9728
0.9562
0.9379
0.9105
0.9145
0.9395
M'O 0,9389
0.8787
0.9139
0.8556
0.8567
0.8948
Oracle
0.9444
0.7825
0,9058
0.8176
0.8098
0.8667
4.3 VISUAL PERMUTATION RECOVERY
We show that O is flexible and can also be used to recover matrix that not in the form [A, PBJ. We can see this from the problem formulation in (I3),, where the cost matrix C(-) can be constructed in other ways as long as it is a function of a permutation. Typically, MCO can be used to solve challeng- ing face image recovery problem. The original face image with size 180 180 Figure Hal comes from the Extend Yale B database (Georghuades et all (IRTI). The corrupted image visualized in Figure B(b). where the pixel blocks with size 30 x 30 in the upper left are shuffled randomly, and 30% of the total pixels are removed. This kind of problem recently con- sidered in (Santa Cruz.er all 201)), which proposes to recover the corrupted image in a data-driven way using convolutional neural networks. However, we show that it is possible to re- cover the image without additional data by merely exploiting the underlying low-rank structure of the image itself.
(a) Original
(b) Corrupted
(c) Baseline
(d) M
Figure Performance of OO
face recovery problem.
This experiment setting is similar to that in (Yao all 2021) but the algorithm in (Yao et all 2021) not be applied since it can not work with the missing values. The MUS algorithm is also not applicable since this problem can not be written in the form of linear regression problem. From Figure H. and H can find that O performs better than the Baseline, and can even recover the original orders of pixel blocks. More results similar to the Figure A and experiment details are provided in Appendix A...
5 CONCLUSION
In this paper, we have studied the important MRUC problem where part of the observed submatrix is shuffled. This problem has not been well explored in the existing literature. Theoretically, we are the first to rigorously analyze the role of low-rank model in the MRUC problem, and is also the first to show that minimizing nuclear norm is provably efficient for recovering a typical low-rank matrix. For practical implementations, we propose a highly efficient algorithm, the M algorithm. which is shown to consistently achieve the best performance over several baselines in all the tested scenarios.
It is worthwhile to point out that apart from the two applications we have studied in this paper, this problem could arise more scenarios like the gnome assembly problem (Huang Madan, 1999), the video pose tracking problem (Ganapathi et al, 2012 and the privacy-aware sensor networks (Ginteser el all pIXE), etc. We believes that our work provides general framework to deal with unknown correspondence issue in these scenarios.
As we have shown in Figure El one major limit of our algorithm is the sensitivity to the initialization. The phenomenon is exacerbated when the additive noise is high the numbers of observable entries are small. We suggest to try with a few different initialization strategy when applying M'O to a specific task. Finding stable initialization strategy is also important task for our future works.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Abubakar Abid, Ada Poon, and James Zou. Linear regression with shuffled labels. arXiv preprint SEt::17005011422 2017.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334-334, 1997.
Garrett Birkhoff.. Three observations on linear algebra. Univ. Nac. Tacuman, Rev. Ser. A, 5:147-151, 1946.
Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix pletion. IEEE Transactions on Information Theory, 56(5):2053 2000200000 2010.
Hock-Peng Chan and Wei-Liem Loh. A file linkage problem of degroot and goel revisited. Statistica Sinica, pp. 1031-1045, 2001.
Debasmit Das and C. George Lee. Sample-to-Sane -ample Correspondence for Unsupervised Domain Adaptation. Engineering Applications of Artificial Intelligence, 73:80 91, August 2018. ISSN 09521976. doi: 10. /016//..ngaappai..... wtw.ppp....1.......... 8.00000. URL http:////awwv.o/////////////////
0103555 arXiv: 1805.00355.
Herbert A David and Haikady N Nagaraja. Order statistics. John Wiley & Sons, 2004.
David S Dummit and Richard Foote. Abstract algebra, volume 1999. Prentice Hall Englewood Cliffs, NJ, 1991.
Varun Ganapathi. Christian Plagemann, Daphne Koller, and Sebastian Thrun. Real-time human pose tracking from range data. In European conference on computer vision, pp. 738-751. Springer, 2012.
A.S. Georghiades, P.N. Belhumeur, and D.J. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Mach. Intelligence, 23(6))643-660, 2001.
Marco Gruteser, Graham Schelle, Ashish Jain, Richard Han, and Dirk Grunwald. Privacy-aware location sensor networks. In HorOS, volume 3, pp. 163-168, 2003.
Paul R Halmos. Measure theory, volume 18. Springer, 2013.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis, 5(4):1-19, 2015.
Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. Matrix completion and low-rank
SVD via fast alternating least squares. The Journal of Machine Learning Research, 16(1):3367- 3402, 2015. Publisher: JMLR. org.
Xiaoqiu Huang and Anup Madan. Cap3: A dna sequence assembly program. Genome research, (9)8668877, 1999.
Pan Ji, Hongdong Li, Mathieu Salzmann, and Yuchao Dai. Robust motion segmentation with un- known correspondence. In European conference on computer vision, pp. 204-219. Springer, 2014.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconm non minimax optimization? PMLR, 2020.
In International Conference on Machine Learning. pp. 4880-4889.
Roy Jonker and Ton Volgenant. Improving the hungarian assignment algorithm. Operations Re- search Letters, 5(4): 1986.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learn ing large incomplete matrices. The Journal of Machine Learning Research, 11:2287-2322, 2010. Publisher: JMLR. org.
10

---

Under review as a conference paper at ICLR 2022
Ashwin Pananjady, Martin J Wainwright, and Thomas A Courtade. Denoising linear models with permuted data. In 2017 IEEE International Symposium on Information Theory (ISIT), pp. 446- 450. IEEE, 2017.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends(R) in Machine Learning, 1165-6)335-607, 2019.
Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould. Deeppermnet: Visual permutation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3949-3957, 2017.
J Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. Collaborative filtering recommender systems. In The adaptive web, pp. 291-324, Springer, 2007.
Martin Slawski, Emanuel Ben-David, and Ping Li. Two-stage approach to multivariate linear regres- sion with sparsely mismatched data. J. Mach. Learn. Res., 21(204):1 2020a.
Martin Slawski, Mostafa Rahmani, and Ping Li. A sparse representation based approach to linear re- gression with partially shuffled labels. In Uncertainty in Artificial Intelligence, pp. 38 48, PMLR, 2020b.
Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, and Martin Vetterli. Unlabeled sensing with random linear measurements. IEEE Transactions on Information Theory, 64(5):3237-3253, 2018.
Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
John Wright and Yi Ma. Digh--Dimesiooal Data Analysis with Low-Dimensional Models: Princi- ples, Computation, and Applications. Cambridge University Press, 2021.
Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. fast proximal point method for computing exact wasserstein distance. In Ryan P. Adams and Vibhav Gogate (eds.), Pro- ceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceed- ings of Machine Learning Research, pp. 433 453. PMLR, 22-25 Jul 2020. URL nttps:
l/proceedingscoo wwwpiiiggs...r..p.m www.mmrr.pprss.. / www.i//11eeuuuu htt//xee2UbBH. I
Yujia Xie, Yixiu Mao, Simiao Zuo, Hongteng Xu, Xiaojing Ye, Tuo Zhao, and Hongyuan Zha. A hypergradient approach to robust regression without correspondence. In International Confer-
ence on Learning Representations, 2021. URL https:
net forum?id
1358B-
raso.
Liu Yang, Ben Tan, Vincent W Zheng, Kai Chen, and Qiang Yang. Federated recommendation systems. In Federated Learning, pp. 225-239. Springer, 2020.
Yunzhen Yao, Liangzu Peng, and Manolis C Tsakiris. Unlabeled principal component analysis.
arXiv preprint arX1v:2101.09446, 2021.
Zinan Zeng. Tsung-Han Chan, Kui Jia, and Dong Xu. Finding correspondence from multiple images via sparse and low-rank decomposition. In European Conference Computer Vision, pp. 325- 339. Springer, 2012.
Hang Zhang and Ping Li. Optimal estimator for unlabeled linear regression. In International Con- ference on Machine Learning, pp. 11153-11163 PMLR, 2020.
Hang Zhang, Martin Slawski, and Ping Li. The benefits of diversity: Permutation recovery in unlabeled sensing from multiple measurement vectors. arXiv preprint 19X9:: 2019a.
Hang Zhang, Martin Slawski, and Ping Li. Permutation recovery from multiple measurement vectors in unlabeled sensing. In 2019 IEFE International Symposium Information Theory (ISIT), pp. 1857-1861. IEFF, 2019b.
Yu Zhang. Bin Cao, and Dit-Yan Yeung. Multi-domain collaborative filtering. arXiv preprint vrXiv:1203.355 2012.
Xiaowei Zhou, Menglong Zhu, and Kostas Danillidis. Multi-image matching via fast alternating minimization. In Proceedings of the IEEE International Conference on Computer Vision, pp. 4032-4040, 2015.
11


Reviews:
[{"review_id": "lV-k9qyiyE_", "reviewer": "Reviewer_CuTB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths: \n\n1. I think this is an interesting problem and the paper is an interesting second step that comes up with an algorithm that more closely respects the structure of the problem than prior work. \n", "summary_of_the_paper": "This paper studies the following matrix recovery problem, given an observation matrix $M_o = [A, \\tilde P B]$, where $\\tilde P$ is an unknown permutation matrix, recover the underlying matrix $M = [A, B]$. The underlying assumption is that the original matrix $M$ is low-rank. They study this in the settings where there are missing entries as well as in the presence of bounded additive Gaussian noise. \n\nPrior work has more extensively considered the version of the problem of multivariate linear regression with unknown correspondence, where the goal is to solve $\\min_{P, W} \\|Y - PXW\\|^2_F$ where $W$ are the regression coefficients, $X$ are the permuted input, and $Y$ is the output. \n\n[1] considers the problem that is solved in this paper as well, but use an extension of the algorithm meant for the regression version of the problem which seems to suffer from the inability to extend to more aggressive noise models. \n\nTheir proof relies on studying how the permutation $P$ changes the rank of the matrix $M$, the authors demonstrate that properties of the cycle decomposition of the permutation $P$ control the rank, qualitatively, the effect of $P$ on $\\text{rank}(M)$ becomes stronger the more rows it permutes and contains less cycles. The program they analyze is the standard nuclear-norm relaxation for the rank function. \n\nThey show that if (1) the singular values of $A, B$ are comparable, (2) the column-space of $M$ can be approximated by the column space of one of its submatrices and (3) The columns of $M$ do not contain any duplicated elements; then the difference between the recovered permutation and original permutation is small (as long as the rank of $M$ is small, the additive noise is bounded. \n\nTo extend this to the case of missing entries requires some technical work which changes the program to nuclear-norm regularized, frobenius norm regression on the coordinates that are present. They solve the problem via an alternating optimization approach -- the regression problem is convex in the unknown matrix $\\widehat M$, and they interpret the problem of recovering the permutation $P$ as an \"entropic optimal transport\" problem, which is strongly convex. \n\nThe authors also run a fairly detailed set of experiments that demonstrate the performance of their algorithm.\n\n\n[1] Unlabeled principal component analysis. -- Yunzhen Yao, Liangzu Peng, and Manolis C Tsakiris'21", "summary_of_the_review": "I think the results are technically interesting and the paper has good motivation, I vote to accept this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Vu3ZkWUEkpn", "reviewer": "Reviewer_2Tsx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strength:\n\n    1. The problem studied in the paper is interesting and of practical value.\n    2. To my knowledge, the theoretical results are novel and interesting, and the proposed algorithm is the first attempt at solving the challenging problem of matrix recovery with missing entries & without correspondences.\n    3. The writting is almost clear, except some inaccuracies on the literature review, technical development, and on language usage (pointed below).\n   \nWeakness:\n\n    1. The literature review is inaccurate, and connections to prior works are not sufficiently discussed. To be more specific, there are three connections, (i) the connection of (1) to prior works on multivariate unlabeled sensing (MUS), (ii) the connection of (1) to prior works in unlabeled sensing (US), and (iii) the connection of the paper to (Yao et al., 2021). \n\n        (i) In the paper, the authors discussed this connection (i). However, the experiments shown in Figure 2 do not actually use the MUS algorithm of (Zhang & Li, 2020) to solve (1); instead the algorithm is used to solve the missing entries case. This seems to be an unfair comparison as MUS algorithms are not designed to handle missing entries. Did the authors run matrix completion prior to applying the algorithm of (Zhang & Li, 2020)? Also, the algorithm of (Zhang & Li, 2020) is expected to fail in the case of dense permutation.\n\n        (ii) Similar to (i), the methods for unlabeled sensing (US) can also be applied to solve (1), using one column of B_0 at a time. There is an obvious advantage because some of the US methods can handle arbitrary permutations (sparse or dense), and they are immune to initialization. In fact, these methods were used in (Yao et al., 2021) for solving more general versions of (1) where each column of B has undergone arbitrary and usually different permutations; moreover, this can be applied to the d-correspondence problem of the paper. I kindly wish the authors consider incoporating discussions and reviews on those methods.\n\n        (iii) Finally, the review on (Yao et al., 2021) is not very accurate. The framework of (Yao et al., 2021), when applied to (1), means that the subspace that contains the columns of A and B is given (when generating synthetic data the authors assume that A and B come from the same subspace). Thus the first subspace-estimation step in the pipeline of (Yao et al., 2021) is automatically done; the subspace is just the column space of A. As a result, the method of (Yao et al., 2021) can handle the situation where the rows of B are densely shuffled, as discussed above in (ii). Also, (Yao et al., 2021) did not consider only \"a single unknown correspondence\". In fact, (Yao et al., 2021) does not utilize the prior knowledge that each column of B is permuted by the same permutation (which is the case of (1)), instead it assumes every column of B is arbitrarily shuffled. Thus it is a more general situation of (1) and of the d-correspondence problem. Finally, (Yao et al., 2021)  discusses theoretical aspects of (1) with missing entries, while an algorithm for this is missing until the present work. \n\n    2. In several places the claims of the paper are not very rigorous. For example,\n        (i) Problem (15) can be solved via linear assignment algorithms to global optimality, why do the authors claim that \"it is likely to fall into an undesirable local solution\"? Also I did not find a comparison of the proposed approach with linear assignment algorithms.\n        (ii) Problem (16) seems to be \"strictly convex\", not \"strongly convex\". Its Hessian has positive eigenvalues everywhere but the minimum eigenvalue is not lower bounded by some positive constant. This is my feeling though, as in the situation of logistic regression, please verify this.\n        (iii) The Sinkhorn algorithm seems to use O(n^2) time per iteration, as in (17) there is a term C(hat{M_B}), which needs O(n^2) time to be computed. Experiments show that the algorithm needs > 1000 iterations to converge. Hence, in the regime where n << 1000 the algorithm might take much more time than O(n^2) (this is the regime considered in the experiments). Also I did not see any report on running times. Thus I feel uncomfortable to see the author claim in Section 5 that \"we propose a highly efficient algorithm\".\n       \n    3. Even though an error bound is derived in Theorem 1 for the nuclear norm minimization problem, there is no guarantee of success on the alternating minimization proposal. Moreover, the algorithm requires several parameters to tune, and is sensitive to initialization. As a result, the algorithm has very lage variance, as shown in Figure 3 and Table 1. \n\nQuestions:\n\n    1. In (3) the last term r+H(pi_P) and C(pi_P) is very interesting. Could you provide some intuition how it shows up, and in particular give an example?\n    2. I find Assumption 1 not very intuitive; and it is unclear to me why \"otherwise the influence of the permutation will be less significant\". Is it that the unknown permutation is less harmful if the magnitudes of A and B are close?\n    3. Solving the nuclear norm minimization program seems to be NP-hard as it involves optimization over permutation matrices and a complicated objective. Is there any hardness result for this problem?\n\nSuggestions: The following experiments might be useful.\n\n    1. Sensitivity to permutation sparsity: As shown in the literature of unlabeled sensing, the alternating minimization of (Abid et al., 2017) works well if the data are sparsely permuted. This might also apply to the proposed alternating minimization algorithm here.\n    2. Sensitivity to initialization: One could present the performance as a function of the distance of initialization M^0 to the ground-truth M^*. That is for varying distance c (say from 0.01:0.01:0.1), randomly sample a matrix M^0 so that ||M^0 - M^*||_F < c as initialization, and report the performance accordingly. One would expect that the mean error and variance increases as the quality of initialization decreases.\n    3. Sensitivity to other hyper-parameters.\n\nMinor Comments on language usage: (for example)\n\n     1. \"we typically considers\" in the above of (7)\n     2. \"two permutation\" in the above of Theorem 1\n     3. \"until converge\" in the above of (14)\n     4. ......\nPlease proofread the paper and fix all language problems.", "summary_of_the_paper": "This paper studies the problem of recovering the ground-truth data matrix from two sub-matrices, where the rows of one submatrix are shuffled by an unknown permutation. For this problem the authors relax the rank minimization formulation into nuclear norm minimization, while it is shown that solving the latter recovers the ground-truth permutation under certain assumptions. The authors further extend the setting to where there could be multiple sub-matrices or missing entries in each sub-matrix, or both, and propose an algorithm of the alternating minization type to solve it. Experiments reveal interesting properties of the problem and algorithm proposed.", "summary_of_the_review": "I think the paper has made some interesting and important contributions to the problem of matrix recovery with missing entries & without correspondences, while there are still a lot of rooms for improvements. Since this is the first work (to my knowledge) that attempts to solve the very challenging problem of MRUC with missing entries, I would like to encourage its publication, hence, for the moment I recommend for weak accept, with the belief that my concerns will be sufficiently addressed in their revised version.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FfS8Wt3wTCC", "reviewer": "Reviewer_Wx9p", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper is well-written and easy to follow. I like the writing style of the paper that uses bold first sentences of important paragraph to summary the main point. \nThe result of the paper is interesting, and could be important as it is one of the few papers on this subject. \nI like the cute result analyzing the perturbation of the rank of the matrix after permutation. \n\nSome concerns:\n- There is the parameter $\\epsilon_3$ in Assumption 3, which appears in the upper bound as the factor $1/\\epsilon_3^2$. Q1: What is the expected scale/order of $\\epsilon_3$ to make the upper bound non-trivial? Q2: Does that order make sense? If I randomly sample a $n$-dim unit vector and calculate the minimal distance between its entries, then I would guess it could be at least smaller than the order of $n^{-3/2}$, because the order of each entry is $O(n^{-1/2})$, and there are $n$ entries. If I set $\\epsilon_3 = O(n^{-3/2})$ by that argument, it becomes a scale of $n^3$ in the upper bound, which might make the upper bound greater than $n$ and thus trivial (since the distance between two permutations is at most $n$).\n\n- Assumption 1 and Assumption 2 basically say that, the singular values and left singular vectors of A and B are close. With these assumptions, one naive algorithm in mind would be, to do SVD of $A$ and the permuted matrix $B$, and find a best matching between their rows, to recover the permutation. For example, one can sort the singular values of each matrices to find a matching between singular values, and use the left singular vectors to do some adjustment for very close singular values (because say if A has a duplicated singular values, we don't know how to match them to the singular values of the permuted B since we don't know which order to map. In this case we can use left singular vectors to help). How do the author think this algorithm would perform, and is there any intuitions that the proposed algorithm in the paper should outperform this method?\n\nSome typos:\n- page 3, 'with multiple permutation' -> 'with multiple permutations'\n- page 6, 'the number of possible correspondence increase' -> 'the number of possible correspondence increases'\n- Page 9, 'provides a general aolution' -> 'provides a general solution'\n\n---------------------- Score after revision -----------------------\n\nI keep my original score, due to the concern that, one might need strong assumptions to make the upper bound of Theorem 1 non-trivial: the parameter $\\epsilon_3$ typically contributes O(n^3) in the upper bound. To make the upper bound non-trivial (that is, o(n)), one might need strong assumptions on other parameters $\\epsilon_1, \\epsilon_2, \\sigma$. Currently I'm not sure if those assumptions make sense in reality.\n\n", "summary_of_the_paper": "This paper studies the matrix recovery with unknown correspondence problem, where we have two data matrices from different sources, with unknown correspondence, and the task is to estimate the underlying correspondence. Mathematically, one can imagine that the row of one data matrix is randomly permuted, and the goal is to recover the permutation. Of course this problem cannot be solved without any conditions, and the condition the author consider is that the joint matrix of the data is low rank.\n\nContribution of the paper:\n- The authors provide theorems to analyze how the random permutation perturb the rank of the data matrix.\n- The authors propose to solve this problem by a nuclear norm minimization problem, and provide theoretical upper bound on the distance between their estimate and the true underlying permutation.\n- The proposed algorithm can work with multiple unknown correspondence, dense permutations, and missing values, which are not achieved by another paper (Yao et al., 2021) on the same subject.", "summary_of_the_review": "Overall I like the idea of the paper and the presentation, however I have one concern about the Assumption 3 and the possibility that the main result (upper bound) in the paper might be trivial in some cases, and hope the author could address that in the rebuttal period.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ELutHPAFmRD", "reviewer": "Reviewer_YsMp", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The strengths are clear - good theoretical analysis, supported with novel practical algorithms.\nMy only criticism (and a minor one) is that the image face example seems contrived. \nIt would be good to see more real world applications (and ones not contrived).", "summary_of_the_paper": "The paper take a scenario - such as recommender systems *federated from different sources so one does not now correspondences* of low rank matrix recovery from partially observed (missing data) and slightly corrupted (small noise) data. It then shows that recovery os theoretically possible and also that an obvious current algorithm candidate will fail but offers a substitute algorithm that works well on the examples given.", "summary_of_the_review": "The application to situations where one knows there are some correspondences (but not the correspondences themselves, for privacy reasons) is sufficiently of general interest. The analysis seems correct and an important contribution. This is further supported with a novel algorithm that is reasonably sufficiently demonstrated on synthetic and real data.\nIn general it seems close to a model paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall this paper was discussed at length given the high variance in scores, and it was ultimately felt that the paper was a borderline paper and there was not enough enthusiasm to warrant acceptance. Several concerns in the discussion could not be resolved, in particular the bounds might not be tight, or even useful, and more explanation on the dependence of various parameters involved and assumptions involved is needed. Specifically, as pointed out by a reviewer, there is a concern about the parameter epsilon_3. It seems for natural input distributions epsilon_3 would be so small that the upper bound would scale as n^3 (given the 1/epsilon_3^2 dependence), which is then trivial since it is larger than n. The reviewers were not satisfied with the authors response regarding this.
Decision: Reject