Year: 2021

Abstract:
We study a matrix recovery problem with unknown correspondence: given the observation matrix Mo = [A, P̃B], where 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, MO (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. MO can also be applied to a more general scenario where we have missing entries in Mo and multiple groups of data with distinct unknown correspondence. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that MO achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.

heading: 1 INTRODUCTION
text: 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 (Unnikrishnan et al., 2018; Gruteser et al., 2003; Das & Lee, 2018). Examples include the multi-image matching problem studied in (Ji et al., 2014; Zeng et al., 2012; Zhou et al., 2015), the record linkage problem (Chan & Loh, 2001) and the federated recommender system (Yang et al., 2020). In the simplest scenario, we have two data matrices A = [a1, ..., an]⊤, B = [b1, ..., bn]⊤ with ai ∈ RmA and bi ∈ RmB , which are from two different platforms (data sources). As discussed above, the correspondence (ai, bi) may not be available, and thereby the goal is to recover the underlying correspondence between a1, ..., an and bπ̃(1), ..., bπ̃(n), 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 Mo = [A, P̃B], where P̃ ∈ Pn is an unknown permutation matrix and Pn denotes the set of all n× n 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, 2021; Mazumder et al., 2010; Hastie et al., 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 (Schafer et al., 2007; Mazumder et al., 2010) and the image recovery and alignment problem (Zeng et al., 2012; Zhou et al., 2015). By denoting Bo = P̃B, we want to solve the following rank minimization problem for MRUC,
min P∈Pn rank([A,PBo]). (1)
Practical applications. It is known that the recommender system often suffers from data sparsity (Zhang et al., 2012) 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 is the multi-domain recommender system considered in (Zhang et al., 2012). Unfortunately, their work neglects a crucial issue that
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 al., 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 to 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 (1) is closely related to the Multivariate Unlabeled Sensing (MUS) problem, which has been studied in (Pananjady et al., 2017; Zhang et al., 2019a;b; Zhang & Li, 2020; Slawski et al., 2020b;a). Specifically, the MUS is the multivariate linear regression problem with unknown correspondence, i.e., it solves
min P∈Pn,W∈Rm2×m1
∥Y − PXW∥2F , (2)
where W ∈ Rm2×m1 is the regression coefficient matrix, Y ∈ Rn×m1 and X ∈ Rn×m2 denotes the output and the permuted input respectively, and ∥·∥F is the matrix Frobenius norm. In fact, a concurrent work (Yao et al., 2021) studies the same rank minimization problem as (1), 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 4, 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 et al., 2021) is the only work that also considers the MRUC problem. Theoretically, (Yao et al., 2021) showed that there exists an non-empty open subset U ⊆ Rn×(m1+m2), such that ∀M ∈ U , solving (1) 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, (Yao et al., 2021) follows the idea of (Slawski et al., 2020b;a) and treats problem (1) 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 perturbed by the permutation, and show that problem (1) can be used to recover a generic low-rank random matrix almost surely. Besides, we also propose a nuclear norm minimization problem as a surrogate for problem (1). The most important theoretical result in this work is that we provide a non-asymptotic analysis to bound the error of the nuclear norm minimization problem under a mild assumption. Practically, we propose an efficient algorithm M3O that solves the nuclear norm minimization problem, which overcomes the aforementioned two shortcomings in (Yao et al., 2021). Notably, M3O works very well even for an extremely difficult task, where we need to recover multiple 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 correspondence, 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 (1) and its convex relaxation in Section 2. Then, the algorithm is developed in Section 3. The simulation results are presented in Section 4 and the conclusions are drawn in Section 5. Notations. Given two matrices X,Y ∈ Rn×m, we denote ⟨X,Y ⟩ = ∑n i=1 ∑m j=1 XijYij as the matrix inner product. We denote X(i) as the ith row of the matrix X and X(i, j) as the element at the ith row and the jth column. We denote 1m ∈ Rm and 1n×m ∈ Rn×m as the all-one vector and matrix, respectively, and In be the n × n identity matrix. For α ∈ Rm, β ∈ Rn, we define the operator ⊕ as α⊕ β = α1⊤n + 1mβ⊤ ∈ Rm×n. We denote ∥ · ∥∗ as the nuclear norm for matrices. For vectors, we denote ∥ · ∥0, ∥ · ∥1 as the zero norm and 1-norm respectively.

heading: 2 MATRIX RECOVERY VIA A LOW-RANK MODEL
text: How is the matrix rank perturbed by the row permutation? To answer this fundamental question, we first introduce the cycle decomposition of a permutation.
Definition 1 (Cycle decomposition of a permutation (Dummit & Foote, 1991)). Let S be a finite set and π(·) be a permutation on S. A cycle (a1, ..., an) is a permutation sending aj to aj+1 for 1 ≤ j ≤ n− 1 and an to a1. Then a cycle decomposition of π(·) is an expression of π(·) as a union of several disjoint cycles1. It can be verified that any permutation on a finite set has a unique cycle decomposition (Dummit & Foote, 1991). Therefore, we can define the cycle number of a permutation π(·) as the number of disjoint cycles with length greater than 1, which is denoted as C(π). We also define the non-sparsity of a permutation as the Hamming distance between it and the original sequence, i.e., H(π) =∑
s∈S I[π(s) ̸= s]. It is obvious that H(π) > C(π) 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 π(·) = (132)(45)(6), and C(π) = 2, H(π) = 5. In all the following theoretical results, we denote the original matrix as M = [A,B] ∈ Rn×m with A ∈ Rn×mA , B ∈ Rn×mB , and rank(M) = r, rank(A) = rA, rank(B) = rB . We denote the corresponding permutation as πP (·) for any permutation matrix P ∈ Pn. 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. ∀P ∈ Pn, we have rank([A,PB]) ≤ min{n,m, rA + rB , r +H(πP )− C(πP )}. (3) We have similar result for the case with multiple permutations, which is summarized in Corollary 1 in Appendix A.1. It turns out that, without any assumption on M , (3) is the tightest upper bound for the rank of a perturbed matrix. Notably, the following proposition says that the upper bound in (3) is attained with probability 1 for a generic low-rank random matrix. Definition 2. A probability distribution on R is called a 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 a random matrix with M = RE where R ∈ Rn×r and E ∈ Rr×m are two random matrices whose entries are i.i.d and follow a proper distribution on R , and r ≤ min{ √ n 2 ,mA,mB}, then ∀P ∈ Pn, the equality rank([A,PB]) = min{2r, r +H(πP )− C(πP )} (4) holds with probability 1. 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 a 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.e., Mo = [Ao, Bo] = [A, P̃B] +W, where W (i, j) ∼ N (0, σ2), where σ2 reflects the strength of the noise. We first denote the singular values of a matrix X ∈ Rn×m as σ1X , ..., σ k X where k = min{n,m}. Since rank(X) = ∥[σ1X , ..., σkX ]∥0, 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 a sparse solution (Wright & Ma, 2021), i.e.,
min P∈Pn
∥[Ao, PBo]∥∗ = ∥[σ1Mo , ..., σ k Mo ]∥1. (5)
Since for an arbitrary matrix, the 1-norm of its singular values is equivalent to its nuclear norm, we refer problem (5) as the nuclear norm minimization problem. Theoretical justification for the nuclear norm. Nuclear norm has a long history used as a convex surrogate for the rank, and it has been theoretically justified for applications like low-rank matrix completion (Candès & Tao, 2010; Wright & Ma, 2021). It is also important to see whether the nuclear norm is still a good surrogate for the rank minimization problem (1). In this work, we establish a sufficient condition on A and B under which problem (5) is provably justified for correspondence recovery. We denote A = ∑rA i=1 σ i Au i Av i⊤ A , B = ∑rB i=1 σ i Bu i Bv i⊤ B as the singular values decomposition of A and B, where the σiA and σ i B are the non-zero singular values. Firstly, from the definition of nuclear norm, it can be simply verified for any P ∈ Pn that −Z/N ≤ (∥[A,PB]∥∗ − ∥M∥∗)/∥M∥∗ ≤ Z/N, (6)
where we denote N = max{∥A∥∗, ∥B∥∗} and Z = min{∥A∥∗, ∥B∥∗}. The inequality (6) indicates that A and B should have comparable magnitude, i.e., ∥A∥∗ ≈ ∥B∥∗, otherwise the influence of 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 1.
1Two cycles are disjoint if they do not have common elements
Assumption 1. There exists a constant ϵ1 ≥ 0 such that
|σiA − σiB | ≤ ϵ1, ∀i = 1, .., r, (7)
where we denote that σiA = 0 if i > rA, and σ i B = 0 if i > rB .
Similar to the matrix rank, we also need a proper low-rank assumption on the matrix M for the nuclear norm. In this work, we particularly study the scenario that the left singular vectors of A and B are similar, which we formally describe as Assumption 2. We refer Assumption 2 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 a constant ϵ2 ≥ 0 such that
∥uiA − uiB∥ ≤ ϵ2,∀i = 1, ..., T, (8)
where we denote T = min{rA, rB}.
Furthermore, we also need that all the column singular vectors u1A, ..., u T A, u 1 B , ..., u T B are variant under any P ∈ Pn with P ̸= In: we define a vector u ∈ Rn to be variant under a P ∈ Pn if Pu ̸= u. One simple and weak condition for a vector u to satisfy such property is that u dose not contains duplicated elements, which leads to the following Assumption 3.
Assumption 3. There exists a constant ϵ3 ≥ 0 such that
min u∈U min i ̸=j |u(i)− u(j)| ≥ ϵ3 > 0, (9)
where U = {u1A, ..., uTA, u1B , ..., uTB}.
In summary, the assumptions mentioned above feature a typical low-rank structure in M , and implies that the nuclear norm of M is sensitive to permutation. With the three assumptions, we have the following important theorem, which provides high probability bound for the approximation error of (5). We denote the solution to (5) as P ∗, and let π∗ and π̃ be the corresponding permutation to the permutation matrices P ∗⊤ and P̃ , respectively. We define the difference between the two permutations π∗ and π̃ as the Hamming distance
dH(π ∗, π̃) def. = n∑ i=1 I(π∗(i) ̸= π̃(i)).
Theorem 1. Under Assumptions 1, 2 and 3, if additionally ϵ1 ≤ M4r , ϵ2 ≤ min{ 1 2 √ 2T , √ 2M 2N }, and σ ≤ M16L2 , then the following bound for the Hamming distance
dH(π ∗, π̃) ≤ 2
ϵ23 2−( √2D D + ( √ 2 + 2)ϵ1r + √ 2ϵ2N + 2 √ 2DLσ − √ Tϵ2 )2 (10) holds with probability at least 1− 2 exp{− D8Lσ}, where L = max{n,m}, D = ∥A∥∗ + ∥B∥∗. The proof to all the aforementioned theoretical results are provided in Appendix A.1.
Remark 1. From Theorem 1 we can see that when ϵ3 > 0, and ϵ1 → 0, ϵ2 → 0, σ → 0, the error dH(π∗, π̃) will converge to zero with probability 1. Furthermore, we can also discover that the correspondence can be difficult to recover when:
• The rank of original matrix M is high, which can be seen from (10). • The magnitude of A and B w.r.t rank or nuclear norm are not comparable, which can be seen
from (6) and (7). • The strength of noise is high, which can be seen from (10) and the probability in Theorem 1. Notably, the numerical experiments in Section 4.1 corroborate our claims as well.
Remark 2. Additionally, from the proof of Theorem 1 we find that the fundamental reason for the success of (5) is that if M satisfies the previous assumptions, we have
∥[A,PB]∥∗/∥M∥∗ ≈ O ( (1−H(πP )/2n)− 1 2 ) . (11)
In many applications, we can only observe part of the full data. Therefore, it is also worthwhile to investigate whether (11) still holds when we can only access a small subset of the entries in Mo. Notably, Figure 1 gives the positive answer and shows that the relationship (11) is gracefully degraded when the percentage of observable entries is decreasing. This phenomenon is remarkable since it indicates the original correspondence can be recovered
from only part of the full data. The matrices used to generate Figure 1 are the same as those in Section 4.1, and the nuclear norm is computed approximately by first filling the missing entries using Soft-Impute algorithm (Mazumder et al., 2010).

heading: 3 ALGORITHM
text: In this section, we consider the scenario with missing values, i.e., our observed data is PΩ(Mo) = PΩ([Ao, Bo]), where PΩ is an operator that selects entries that are in the set of observable indices Ω. In this scenario, problem (5) 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 et al., 2015; Mazumder et al., 2010), we propose to solve an alternative form of (5) as follows,
min M̂∈Rn×m min P∈Pn ∥∥∥PΩ([Ao, PBo])− PΩ(M̂)∥∥∥2 F + λ ∥∥∥M̂∥∥∥ ∗ , (12)
where λ > 0 is the penalty coefficient. We denote that M̂ = [M̂A, M̂B ] and M̂A, M̂B are the two submatrices with the same dimension as Ao and Bo respectively. We can write (12) equivalently as
min M̂∈Rn×m min P∈Pn ∥∥∥PΩ(Ao)− PΩ(M̂A)∥∥∥2 F + ⟨C(M̂B), P ⟩+ λ ∥∥∥M̂∥∥∥ ∗ , (13)
where C(M̂B) ∈ Rn×n is the pairing cost matrix with C(M̂B)(i, j) = ∑
(j,j′′)∈Ω
( M̂B(i, j ′′)−Bo(j, j′′) )2 , ∀i, j = 1, ..., n.
Baseline algorithm. A conventional strategy to handle an optimization problem like (13) is the alternating minimization or the block coordinate descent algorithm (Abid et al., 2017). Specifically, it executes the following two updates iteratively until it converges.
M̂ new ← argmin M̂∈Rn×m ∥∥∥PΩ([Ao, P̂ oldBo])− PΩ(M̂)∥∥∥2 F + λ ∥∥∥M̂∥∥∥ ∗ , (14)
P̂ new ← argmin P∈Pn ⟨C(M̂ newB ), P ⟩. (15)
The first update step (14) is a convex optimization problem and can be solved by the proximal gradient algorithm (Mazumder et al., 2010). The second update step (15) is actually a discrete optimal transport problem which can be solved by the classical Hungarian algorithm with time complexity O(n3) (Jonker & Volgenant, 1986). However, as we will see in the Section 4, 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 (15) is often not unique and a small change in M̂B would lead to large change of P̂ . To address this issue, we propose a novel and efficient algorithm M3O algorithm based on the entropic optimal transport (Peyré et al., 2019) and min-max optimization (Jin et al., 2020). Smoothing the permutation with entropy regularization. For any a ∈ Rn, b ∈ Rm, we define Π(a, b) = {S ∈ Rn×m : S1m = a, S⊤1n = b, S(i, j) ≥ 0, ∀i, 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 Π(1n,1n) is equal to Pn. Inspired by (Xie et al., 2021) and the interior point method for linear programming (Bertsekas, 1997), in order to smooth the optimization process of the baseline algorithm, we relax P from being an exact permutation matrix, i.e., to keep P staying inside the Birkhoff polytope Π(1n,1n). That is, we propose to replace the combinatorial problem (15) with the following continuous optimization problem
min P∈Π(1n,1n) ⟨C(M̂B), P ⟩+ ϵH(P ), (16)
where H(P ) def.= ∑
i,j P (i, j)(log(P (i, j)) − 1) is the matrix negative entropy and ϵ > 0 is the regularization coefficient. Notably, (16) is also known as the Entropic Optimal Transport (EOT) problem. According to (Peyré et al., 2019), (16) is a strongly convex optimization problem with respect to 1-norm and can be solved roughly in the O(n2) complexity per iteration by the Sinkhorn algorithm. Specifically, the Sinkhorn algorithm solves the dual problem of (16),
max α,β∈Rn
Wϵ(M̂B , α, β) def. = ⟨1n, α⟩+ ⟨1n, β⟩ − ϵ ⟨ 1n×n, exp { α⊕ β − C(M̂B)
ϵ
}⟩ , (17)
which reduces the variables dimension from n2 to 2n and is thus greatly favorable in the high dimension scenario. By substituting the inner minimization problem of (13) with (16), we end up with solving the following unconstrained min-max optimization problem
min M̂ max α,β ∥∥∥A− M̂A∥∥∥2 F +Wϵ(M̂B , α, β) + λ ∥∥∥M̂∥∥∥ ∗ . (18)
Follows the idea of (Jin et al., 2020), we consider to adopt a proximal gradient algorithm with a Max-Oracle for (18). Specifically, we employ the Skinhorn algorithm (Peyré et al., 2019) as the MaxOracle to retrieve an ε-good solution of the inner max problem (17). We summarize our proposed algorithm M3O (Matrix recovery via Min-Max Optimization) in Algorithm 1, where proxλ∥·∥∗(·) is the proximal operator of nuclear norm and ρk is the gradient stepsize. The convergence property of M3O can be obtained by following (Jin et al., 2020), which shows that, with a decaying stepsize, M3O is bound to converge to an ε-good Nash equilibrium within O(ε−2) iterations.
Algorithm 1: M3O 1 while not converged do 2 For the tolerance ε, run the Sinkhorn algorithm to find α∗, β∗ such that
Wϵ(M̂ k B , α ∗, β∗) > max α,β Wϵ(M̂ k B , α, β)− ε;
3 Perform M̂ k+1 ← proxλ∥·∥∗(M̂ k − ρk∇M̂Fϵ(M̂ k, α∗, β∗)), where Fϵ(M̂, α, β) def. = ∥∥∥A− M̂A∥∥∥2
F +Wϵ(M̂B , α, β);
4 end
Remark 3. A recent work (Xie et al., 2020) proposes a decaying strategy for the entropy regularization coefficient ϵ in (16) so that the optimal solutions of (15) and (16) do not deviate too much. Inspired by it, in our practice, we take large ϵ in the beginning and gradually shrink it by half until the objective function stops improving for K steps. Remark 4. A useful trick is that we should not take large stepsize ρk in the early iterations because the permutation matrix could still be far away from the optimal one. However, a small stepsize would lead to slow convergence. Heuristically, we propose an adaptive stepsize strategy that performs well in practice. For the solution of (16) P̂k at the kth iteration, we compute the two statistics
δk = ∥∥∥P̂k−1 − P̂k∥∥∥2
F /2n and ck = ∥∥∥maxjP̂k(·, j)− 1n∥∥∥ 1 /n.
Here δk represents how fast the permutation matrix P̂k changes over the iterations, while ck measures how far the current P̂k is close to an exact permutation matrix. Both δk and ck reflect the confidence on the current found correspondence. Based on them, we set the stepsize as ρk+1 = (1−δk)(1−ck)ω, where ω > 0 is a tunable parameter which is often set to a value between 0.5 to 3. ω actually trades off the convergence speed and final performance. The smaller the ω, the faster the convergence. Therefore, a practical way is to start with a small ω, and gradually increase it until the final performance stops improving. Remark 5. As discussed in Section 1, in many cases we have to deal with the problem that involves multiple correspondence, i.e., we need to recover the matrix M = [A,B1, ..., Bd] from the observation data PΩ(Mo), where
Mo = [Ao, B 1 o , ..., B d o ] = [A, P̃1B1, ..., P̃dBd] +W,
where P̃l ∈ 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 exponentially as d grows, the complexity of M3O per iteration only linearly increases with d and can be implemented in a fully parallel fashion. Specifically, in this scenario, we solve the problem
min M̂ min P1,...,Pd ∥∥∥PΩ(Ao)− PΩ(M̂A)∥∥∥2 F + d∑ l=1 { ⟨C(M̂Bl), Pl⟩+ ϵH(Pl) } + λ ∥∥∥M̂∥∥∥ ∗ , (19)
s.t. Pl ∈ Π(1n,1n), l = 1, ..., d,
where we denote M̂ = [M̂A, M̂B1 , ..., M̂Bd ]. Here M̂A and M̂Bl have the same dimension with Ao and Blo, respectively. One can find that the inner problems for solving Pl are actually decoupled for each l, which guarantees an efficient parallel implementation. Remark 6. Since x problem (12) has a similar form to that considered in (Mazumder et al., 2010). We adopt the same tuning strategy of λ as in (Mazumder et al., 2010), which suggests that we should start with large λ and gradually decrease it. We relegate more details about M3O to Appendix A.6.
4 EXPERIMENTS
In this section, we evaluate our proposed M3O on both synthetic and real-world datasets, including the MovieLens 100K and the Extended Yale B dataset. We also provide an ablation study for the decaying entropy regularization strategy and the adaptive stepsize strategy proposed in Remarks 3 and 4. In all the experiments, we employ the Soft-Impute
algorithm (Mazumder et al., 2010) as a standard algorithm for matrix completion. Extra experiment details and auxiliary results can be found in Appendix A.9. 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 (14) and (15). 3. MUS: Since there is currently no existing algorithm directly applicable to the scenario consid-
ered by (19), inspired by (Yao et al., 2021), we modify and extend the algorithm in (Zhang & Li, 2020), 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.8.

heading: 4.1 SYNTHETIC DATA
text: We first investigate the property of our proposed M3O algorithm on the synthetic data. Data generation. We generate the original data matrix in this form M = RE + ηW, where R ∈ Rn×r, E ∈ Rr×m, W ∈ Rn×m and η > 0 indicates the strength of the additive noise. The entries of R, E, W are all i.i.d sampled from the N (0, 1). Then we split the data matrix M by M = [A,B1, ..., Bd] where we denote A ∈ Rn×mA , B1 ∈ Rn×m1 , ..., Bd ∈ Rn×md to represent data from d + 1 data sources. The permuted observation matrix Mo is obtained by first generating d permutation matrices P1, ..., Pd randomly and independently, and then computing Mo = [A,P1B1, ..., PdBd]. Finally, we remove (1 − |Ω| · 100%/(n ·m)) percent of the entries of Mo randomly and uniformly, where |Ω| indicating the number of observable entries. Ablation study. We denote the following variants of M3O for the ablation study.
1. M3O-AS-DE: M3O with both Adpative Stepsize and Decaying Entropy regularization. 2. M3O-DE: M3O with Decaying Entropy regularization only. M3O-DE-1 and M3O-DE-2 adopt
constant stepsize ρk = 0.5 and ρk = 0.01, respectively. 3. M3O-AS: M3O with Adpative Stepsize only. The entropy coefficient ϵ is fixed to 0.0005.
In the following results, we denote πl as the corresponding permutation to Pl. We initialize M̂ from Gaussian distribution for the M3O algorithm and its variants. We choose initial ϵ as 0.1 and K = 100 as the default for the decaying entropy regularization, and set ω = 3 as the default for the adaptive stepsize. We also report the achieved objective values of (19) for the tested algorithms, except for the MUS algorithm since it has a different objective. We denote π̂ as the recovered permutation. Results. Figure 2 displays the result under the setting η = 0.1, |Ω| · 100%/(n · m) = 80%, n = m = 100, r = 5, d = 1, mA = 60 and m1 = 40. The algorithm M3O-AS-DE achieves the best result, and can recover the ground-truth correspondence. M3O-AS behaves similarly to Baseline
and MUS. They all converge to a poor local solution quickly. M3O-DE-1 converges quickly and also falls into a poor local solution due to large stepsize, while M3O-DE-2 adopts a small stepsize and hence suffers from slow convergence. Due to the superiority of M3O-AS-DE over the other variants, in the following results, we refer M3O as M3O-AS-DE for short. Figure 3 examine M3O on a 1-correspondence problem under different regimes w.r.t |Ω|, η, r and mA/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 in Remarks 1 and 2. Finally, we examine M3O on a few d-correspondence problems. See Table 1 for various results, where we set r = 5 and ε = 0.1. Notice that for the 4-correspondence problem in the table, there are (100!)4 possible correspondence. Even for such a difficult problem, M3O is able to recover 61.5% of the ground-truth correspondence with a good initialization.
Table 1: Performance of M3O for various d-correspondence problems. The normalized permutation error∑d l=1 dH(π̂l, πl)/d is reported as mean±std (min) over 10 different random initializations.
(n,mA,m1, ...,md) d |Ω| · 100%/(n ·m)
∑d
l=1 dH(π̂l, πl)/d
(100,40,30,30) 2 40% 33.35± 32.85 (0.00) (100,20,40,40) 2 40% 58.90± 27.21 (2.00)
(100,45,25,25,25) 3 50% 61.97± 15.41 (37.33) (100,40,25,25,25,25) 4 60% 59.90± 13.64 (38.50)

heading: 4.2 MULTI-DOMAIN RECOMMENDER SYSTEM WITHOUT CORRESPONDENCE
text: In this section, we study the performance of M3O on a real world dataset MovieLens 100K2, which is a widely used movie recommendation dataset (Harper & Konstan, 2015). In this application, we mainly focus on the metric Root Mean Squared Error (RMSE), i.e.,
RMSE def.=
√ 1
N ∑ i,j (M̂ij −Mij)2.
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 (Zhang et al., 2012). We extract five most popular genres, which are Comedy, Romance, Drama, Action, Thriller respectively, to define the data from 5 different domains (or platforms). In addition to (Zhang et al., 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 as 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-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 M3O. Table 2 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 harmful to the overall performance since it is even worse than the results of SIC. Notably, although the ground-truth correspondence can not be recovered, each platform can still benefit from M3O since it
2https://grouplens.org/datasets/movielens/100k/
improves the performance over SIC. This is mainly because M3O 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. Remarkably, M3O is only inferior to the Oracle method a little, and even achieves lower test RMSE than the Oracle method on the Comedy genre.
4.3 VISUAL PERMUTATION RECOVERY
(a) Original (b) Corrupted
(c) Baseline (d) M3O
Figure 4: Performance of M3O on a face recovery problem.
We show that M3O is flexible and can also be used to recover matrix that is not in the form [A,PB]. We can see this from the problem formulation in (13), where the cost matrix C(·) can be constructed in other ways as long as it is a function of a permutation. Typically, M3O can be used to solve a challenging face image recovery problem. The original face image with size 180×180 in Figure 4(a) comes from the Extend Yale B database (Georghiades et al., 2001). The corrupted image is visualized in Figure 4(b), where the pixel blocks with size 30×30 in the upper left are shuffled randomly, and 30% of the total pixels are removed. This kind of problem is recently considered in (Santa Cruz et al., 2017), which proposes to recover the corrupted image in a data-driven way using convolutional neural networks. However, we show that it is possible to recover the image without additional data by merely exploiting the underlying low-rank structure of the image itself.
This experiment setting is similar to that in (Yao et al., 2021) but the algorithm in (Yao et al., 2021) can 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 4(c) and 4(d) we can find that M3O performs better than the Baseline, and can even recover the original orders of pixel blocks. More results similar to the Figure 4 and experiment details are provided in Appendix A.9.

heading: 5 CONCLUSION
text: 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 M3O 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 in 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 (Gruteser et al., 2003), etc. We believes that our work provides a general framework to deal with unknown correspondence issue in these scenarios.
As we have shown in Figure 3, one major limit of our algorithm is the sensitivity to the initialization. The phenomenon is exacerbated when the additive noise is high or the numbers of observable entries are small. We suggest to try with a few different initialization strategy when applying M3O to a specific task. Finding stable initialization strategy is also an important task for our future works.

Review summaries:
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.  Contribution of the paper: - The authors provide theorems to analyze how the random permutation perturb the rank of the data matrix. - 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. - 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.

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.

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.   Prior 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.   [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.   Their 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.   They 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.   To 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.   The authors also run a fairly detailed set of experiments that demonstrate the performance of their algorithm.   [1] Unlabeled principal component analysis. -- Yunzhen Yao, Liangzu Peng, and Manolis C Tsakiris'21