Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

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.
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. 
The result of the paper is interesting, and could be important as it is one of the few papers on this subject. 
I like the cute result analyzing the perturbation of the rank of the matrix after permutation. 

Some concerns:
- 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$).

- 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?

Some typos:
- page 3, 'with multiple permutation' -> 'with multiple permutations'
- page 6, 'the number of possible correspondence increase' -> 'the number of possible correspondence increases'
- Page 9, 'provides a general aolution' -> 'provides a general solution'

---------------------- Score after revision -----------------------

I 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.


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.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: 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.
main_review: The strengths are clear - good theoretical analysis, supported with novel practical algorithms.
My only criticism (and a minor one) is that the image face example seems contrived. 
It would be good to see more real world applications (and ones not contrived).
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.
In general it seems close to a model paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

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
main_review: Strengths: 

1. 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. 

summary_of_the_review: I think the results are technically interesting and the paper has good motivation, I vote to accept this paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: Strength:

    1. The problem studied in the paper is interesting and of practical value.
    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.
    3. The writting is almost clear, except some inaccuracies on the literature review, technical development, and on language usage (pointed below).
   
Weakness:

    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). 

        (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.

        (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.

        (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. 

    2. In several places the claims of the paper are not very rigorous. For example,
        (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.
        (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.
        (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".
       
    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. 

Questions:

    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?
    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?
    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?

Suggestions: The following experiments might be useful.

    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.
    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.
    3. Sensitivity to other hyper-parameters.

Minor Comments on language usage: (for example)

     1. "we typically considers" in the above of (7)
     2. "two permutation" in the above of Theorem 1
     3. "until converge" in the above of (14)
     4. ......
Please proofread the paper and fix all language problems.
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.
review_title: null

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