Unlabeled Principal Component Analysis
Authors: Yunzhen Yao
Liangzu Peng
Manolis C. Tsakiris
Venue: NeurIPS 2021 Poster (2021)
Keywords: unlabeled sensing
linear regression without correspondences
robust principal component analysis
algebraic geometry

Abstract: We introduce robust principal component analysis from a data matrix in which the entries of its columns have been corrupted by permutations, termed Unlabeled Principal Component Analysis (UPCA). Using algebraic geometry, we establish that UPCA is a well-defined algebraic problem in the sense that the only matrices of minimal rank that agree with the given data are row-permutations of the ground-truth matrix, arising as the unique solutions of a polynomial system of equations. Further, we propose an efficient two-stage algorithmic pipeline for UPCA suitable for the practically relevant case where only a fraction of the data have been permuted. Stage-I employs outlier-robust PCA methods to estimate the ground-truth column-space. Equipped with the column-space, Stage-II applies recent methods for unlabeled sensing to restore the permuted data. Experiments on synthetic data, face images, educational and medical records reveal the potential of UPCA for applications such as data privatization and record linkage.

Unlabeled Principal Component Analysis
Yunzhen Yao, Liangzu Peng, Manolis C. Tsakiris
School of Information Science and Technology ShanghaiTech University
Abstract
We introduce robust principal component analysis from data matrix which the entries of its columns have been corrupted by permutations, termed Unlabeled Principal Component Analysis (UPCA). Using algebraic geometry, we establish that UPCA is well-defined algebraic problem in the sense that the only matri- ces of minimal rank that agree with the given data are row tow-permutations ground- -ruund-tuuthhuo matrix, arising the unique solutions of polynomial system of equations. Further, we propose an efficient two-stage algorithmic pipeline for UPCA suitable for the practically relevant where only fraction of the data have been permuted. Stage-I employs outlier-robust PCA methods to estimate the ground-truth column-space. Equipped with the column-space. Stage-II applies recent methods for unlabeled sensing to restore the permuted data. Experiments on synthetic data, face images, educational and medical records reveal the potential of UPCA for applications such as data privatization and record linkage.
the
Introduction
1.1 Motivation
In principal component analysis, a cornerstone of machine learning and data science, one is given data matrix X, assumed to be a corrupted version ground-truth data matrix X* = [x- ... x E Rmxn, typically but not necessarily assumed to have low rank, and the objective is to estimate X* or the column-space S* C Th. of X* The most common types of corruptions that have attracted interest in modern studies additive sparse perturbations [6 47). outlier data points that lie away from S* 43 [40] and missing entries, the latter also known as low-rank matrix completion 47.
Recently, permutations have been emerging as another type of data corruption, typically set in the context of linear regression, where the correspondences between the input and the output data have been partially distorted one is given point x" of a linear subspace S*, but only up to a permutation
30 31 46 19 41 33). There, its coordinates, say & = x""x with IT* unknown permutation, and the goal to find x* from the data x, S". This
entirely unavailable [38 39 22
Unlabeled Sensing (38 39 problem has many potential machine learning applications, e.g., record permutation learning, and matching problems
linkage [30 31, visual 26 27 textual 28 29
in neuroscience 21 and biology
While methods for unlabeled sensing rely knowledge of the source subspace S*, this is not always known in practice. On the other hand, data of the form X = [ x,,],,,, E R with X, [T an unknown permutation of an unknown point x E S*, are often available, thus raising the question of whether S* can be estimated from X. An important example of this situation record linkage [3 20 3], where the objective is to integrate data from independent sources, , &n E m for subsequent data analysis. Since the entries of different records š; 's are collected separately, the data matrix X is unlabeled the sense that, the entries of its i-th row do not necessarily correspond
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to the same entity. Such kind of unlabeled data X also arise in the context of data privatization, where the data provider anonymizes the original data X by permuting each column of X prior to release [1] [6] Data re-identification is a concern since companies with privacy policies, health care providers, and financial institutions may release the collected data after anonymization. Understanding the fundamental limits of re-identifying the original data X* from the released ones X is essential for striking balance between data privacy and data preservation, the subject of a plenary talk in the 2019 International Conference on Machine Learning (2).
1.2 Contributions
In this paper we consider the recovery of X from its unlabeled version X, which we term Unlabeled Principal Component Analysis (UPCA). We make the following contributions:
We establish that as long as := rank (X*) ] < min(m, n) and X* is generic (see Definition D. then up permutation of its rows, X is the only matrix of rank less than or equal that is compatible with X. This asserts that UPCA is well-posed problem, since the inherent ambiguity of whether X comes from X row-permuted version of X is in most cases practically harmless.
We establish that in this basic formulation UPCA is purely algebraic problem, by exhibiting polynomial system of equations parametrized by X, whose solutions are all the row- permutations of X"; solving the UPCA problem amounts to obtaining one such solution.
Inasmuch as solving this polynomial system is in principle NP-hard, we introduce an efficient algorithmic pipeline for the practically relevant case where significant part of the data have undergone the same permutation, while the rest of the points have been permuted arbitrarily; in the case of record linkage this would correspond one of the records having much larger size than the others. The first stage of the pipeline employs PCA methods with robustness to outliers
33 45 37
to produce an estimate $ of S* from X; the second stage 36 to furnish an estimate & of
of the pipeline uses unlabeled sensing methods 30
X from and X.
We introduce a simple but efficient algorithm for unlabeled sensing based on least-squares with recursive filtration (Algorithm 2)
We assess our algorithmic pipeline on synthetic data, face images, educational and medical records, with encouraging results.
1.3 Related work
Unlabeled sensing. There a large literature on application-speeifie problems that involve lack of correspondences, c.g. in computer vision statistics; here we just review four recent methods for unlabeled sensing that will be used in this paper. In unlabeled sensing one is given a subspace S* C m of dimension and point X which is some permuted version of point x* E S* and the goal is to recover x" from S* and x. A critical distinction among methods in the literature is the sparsity level & of the permutation, that is the ratio of coordinates that are moved by the permutation.
The case of dense permutations (a 1) is extremely challenging, with existing methods only able to handle small ranks We consider two methods known to perform best in this regime. The first one the algebraic-geoment instead concentrates its effort on solving a polynomial system of r equations in variables to produce an initialization for an expectation maximization algorithm. Currently, this method is efficient for < 5 and intractable otherwise. A very different method is CCV-Min of (23]. which proceeds via Franch-&-bourr together with concave minimization and can handle ranks S
AIEM method of [36]. This has linear complexity
m and
The -RR algorithm of (30) applies an é robust linear regression relaxation, and it works when a S 0.5. Another approach is the Pseudo-Likelihood method (PL) of [32), which fits two-component mixture density for each entry of x, one accounting for fixed data and the other for permuted data. The fitting is done via a combination of hypothesis testing, reweighed least-squares, and alternating minimization. Empirically, PI. can tolerate up to a = 0.7 but it sensitive the particular basis of S* used to generate x.
For sparse permutations (small a) dealing with higher ranks becomes possible 30 32

---

Robust PCA with outliers. PCA methods with robustness to outliers will also play role in this paper. Among a large literature, we review four modern methods. In that context, it is assumed that X can be partitioned into inlier points that lie in an unknown r-dimensional subspace S I t and outlier points that lie away from S", and the goal is to recover S* from X. The Outlier Pursuit (OP) method of [3] decomposes X via convex optimization into the sum of low-rank and Dolumn-sparss parts. The convex method of [45], a successor of [3], referred to as Self-Expr, solves a self -xpressxeees clastic net problem so that each xj is expressed an &2 -rrguularized sparse linear combination of the other points. The self-expressive coefficients define transition probabilities of a random walk on a graph, and the average of the t-step transition probability distributions is used
score for inliers vs. outliers, with higher scores expected for the former. The Coherence Pursuit (CoP) method of [2 is based on the following simple but effective principle: with X-, the matrix X with column j removed, for each Xj one computes its coherence X_,;; with the rest of the points. As it turns out, inliers tend to have coherences of higher 22-norm than outliers, and the top r Xj are taken span S. Finally, the Dual Principal Component Pursuit (DPCP) of (37) solves an & non-smooth problem on the Grassmannian via herated-reweiihhed least-squares (IRLS), to compute an orthonormal basis for the orthogonal complement of the subspace. A dual formulation with a randomized singular value decomposition incorporated in the IRLS procedure is known as Fast Median Subspace [18] In sharp contrast to other convex robust-PCA methods, DPCP has been shown in 48 to tolerate as many outliers as the square of the number of inliers.
2 Theoretical Foundations
2.1 Problem Formulation
Let us denote by Pm the set of all permutations of coordinates of IR"", We let X [x ... x; Rmxn be our ground-truth data matrix with rank r < min(m, n. and column-space S = C(X*), and we suppose that the available data are
X [ ... Xnl = [1}x ... ........ xxxx E mm
(1)
where each IT; E Pm is unknown permutation. Let Pn = [i) Pm be ordered copies of Pm. where [n] = (1....,n) n]. For π = (II...., [T)) E Pm we set π(()= = 1 - II X,J. We pose Unlabeled Principal Component Analysis (UPCA) the following rank minimization problem:
min rank ((X)
(2)
TEPM
First, note that (2) never has a unique solution, because if π = (I.,...., ITn) π = (IIII,,..... IIIT,,, where IT Pm any permutation. This reveals an inherent ambiguity of UPCA: it is only possible to recover X* from X up to a permutation ITX* of its rows. On the other hand, this is rather harmless in many situations, since TTX is the same dataset as X* except that the row-features appear now in some different order. Thus, our hope in formulating 2 that III,; ) with ranging across Pm. and 11; as in [I. However, without any other assumptions on the data X', there could in principle be additional undesired permutations that also give rank X*, or even worse, the minimum rank in (2) could be
is a solution, then so
the only solutions are of the form π = (IIIT;
lower than rank X* Our results show that for generic enough data, such pathological situations
do not occur, and the only solutions to are the ones associated with oowppermutations of X*.
2.2 Elements of Algebraic Geometry
Before stating our results, make the notion of generic precise using some basic algebraic geometry R 15
Let Z = (2i5) be an m x n matrix of variables Zij and [R|Z] = IR [Zı5 i E [m],) E [n]] the ring of polynomials in the Zij 's with real coefficients. An algebraic variety of RRn is the set of solutions of polynomial system of equations in IR [Z). In particular, the set of (r 1) x [r 1) determinants of Z are polynomials in Zij 's of degree r + and define the algebraic variety
M, (X E m rank X <T),
since a matrix X E RRmx has rank at most r if and only if all (r + 1) x (r + 1) determinants of zero.
3

---

The algebraic variety M, admits a topology, called Zariski topology, which makes it convenient to work with. The closed sets in this topology are the algebraic subvarieties of M, These are sets of matrices of rank S which in addition satisfy certain other polynomial equations in RRZ] For example, the set of matrices of rank at most 1 a proper closed subset of Mr. because in addition to the equations defining Mr it is further defined by requiring all r determinants to be zero. Open sets in M, are defined as complements of closed sets, or equivalently they are defined by requiring that certain sets of polynomials are not all simultaneously zero. For example, the set of matrices of rank exactly equal to is a proper open subset of M, defined by the non-simultancous vanishing of all determinants are zero and least one T x T determinant is zero. Now, the algebraic variety M, is irreducible in the sense that it can not be described the union of two proper algebraic subvarieties of it. A consequence of this is that non-empty open sets of Mr have the very important property of being topologically dense. This means that given non-empty open set l C M, and a point E Mr, every neighborhood of X intersects 4. It follows that under any non-degenerate continuous probability measure on M,, non-empty Zariski-open set of M, has measure 1. For example, the set of matrices in Mr of rank T is non-empty and open, and thus it is dense. Hence a randomly sampled matrix in Mr under a continuous probability measure will have rank with probability 1, We refer to such a fact by saying that a generic matrix in M, has rank r. More generally:
determinants of Z; matrix has rank if and only if all (r + 1) x (T + 1)
Definition 1. We say that a generic matrix in MM satisfies a property, if the property is true for every matrix in non-empty open subset of Mr.
2.3 UPCA is a Well-Posed Problem
Our main theoretical result i
Theorem 1, For X" a generic matrix in Mr, we have that rank π(X) 2 r for any π E Pn, with equality if and only if [Xx = IIX* for some IT E Pm-
Theorem says that for X M, generic, and up a permutation of the coordinates of R. t S* is the unique r-dimensional subspace that explains the data X in the UPCA sense, and rank X* is the minimum objective in (
2.4 UPCA is an Algebraic Problem
How can one go about solving the discrete optimization problem 2)? In general, brute force selection of the IT 's has complexity ((m!)",, which is out of the question. On the other hand, problem (2) has a rich algehraic structure, which we harvest by showing that X", up to a permutation of rows, arises as the unique solution to polynomial system of equations.
To begin with, for each E [n] and each e [m], we define the following column-symmetric polynomials of R[Z]:
DZ) = Σ z/
ic(m)
Pt.j (Z) == Pc.j - Pe,5
Note that Pe.5 ( Z)) = (Z) for any π E Pm and thus Pt.j (X) = (X*) Now let us think of X E M, as a product of two matrices of size m r and r x n. and let us define another polynomial ring with variables associated to these two factors. For r +r+,,..,, m. and k E [r] and E [n), we let bik, Ckj be new set of variables over R. Organize the bi 's to occupy the (m r) x bottom block of an m x r matrix whose top r X r block is the identity matrix size r, and the C15² 's into a x n matrix the j-th column of C. With Xıj, xi, the i-th coordinate of X;, x respectively, we obtain polynomials
(Cuj). For i E [m], we write b. for the i-th row of B; for j E [n], we write cj for
qe,j for E [m], j E [n] of [B, C] by substituting Zij- + b, cj in the Pt,j (Z)ss above:
de.j(B, C) := (BC) (x)
Σ 1e/m]
(bTTc,)=-
Σ X
Σ (bTc))
Σ xij
l [m]
[m]
(e(m)
'The proof's of Theorems can be found in 44

---

The set of common roots of all qe, defines an algebraic variety that depends only on X", given by
Vxx- = (B', C') T x R [t,; , c') =0 v4 E [m], vj E [n]; ((H).rr) = I,),
where frr, I, signifies that the top r T block of B' mm is the identity matrix. Let us get a feeling about the points of yx-. With Pm. if the column-space C(IIX*) of TIX* does not drop dimension upon projection onto the first coordinates, then there exists unique basis B of C(II**)
with the identity matrix occurring at the top r x block. In that case, there a unique factorization =Bii Ci and the point (Bi Cii) lies in the variety Vx- because
ITX"
qt, (Bi, Ch Pe,, C+t -e,)) Pt,
Pe, (TIX*) Pe)(X = Pr,( - Pt,j O.
Our second result says that if X* is generic, then all points of 3'x are of this type. That is, they correspond to factorizations Bi Ct of TTX* as varies across all permutations:
Theorem 2. For generic matrix X in Mr have
V/- {BB,, CiT) E IR
x RT T | E Pmi Br,,r) = 1;; rIx = B
Thanks to Theorem we have the following important conceptual finding. Assuming X is generic, to obtain X up to some permutation of its rows from X, one needs to compute an arbitrary root (B', C') of the polynomial system of equations
9c, (B, C) = 0, vl E [m], Vj [n]
and multiply its factors to get B'C', Developing polynomial system solver for UPCA would involve two main challenges: attaining robustness to noise and scalability, with the former typically easier to deal with than the latter. We leave such an endeavor to future research.
2.5 UPCA with Dominant Permutations
We close this section with a special case of interest, where part of the data have undergone the same dominan! permutation; in fact, given the inherent ambiguity of UPCA discussed above, we may as well take this dominant permutation to be the identity matrix Im of size m x m. To make this precise, we define the multiplicity μulI) of a permutation I1 E Pm to be the number of times that IT appears as II I1; in ① with j ranging in [n). We have:
Theorem 3. Suppose that u(Im) 2 while u(Il) < T for any other IT + Im Then for generic X" E Mp, we have that S* is the unique solution the following consensus maximization problem
max SST
#[3g R2 E S; E [n]],
(4)
where denotes the cardinality of a set, and the maximization taken over all subspaces S C Rmm of dimension I T.
Theorem says that for sufficiently generic ground truth data X", the given data X admit a natural partition into set of inliers and outliers with respect to the linear subspace S*:
X = (2, & E S*), X = (Xg
R g S*)
Of course we do not know what the partition into inliers and outliers is, because we do not know what S* is. But the presence of this geometric structure is enough for PCA methods with robustness to outliers to operate on X in order to estimate S*. The rest of the paper proceeds algorithmically building on this insight.
Algorithms
3.1
Two-stage algorithmic pipeline for UPCA
We saw in the previous section that the UPCA problem (2) well-defined (Theorem I and in principle solvable by a polynomial system of equations (Theorem 2 However, this polynomial system is at the moment intractable solve even for moderate dimensions. On the other hand, Theorem 3 suggests the following algorithmic pipeline, for the case where there is dominant
5

---

permutation, which we can take to be the identity as in the theorem. At Stage-I of the pipeline, a PCA method with robustness to outliers 43
18 is employed to produce an estimate $ of S from X. At Stage-II of the pipeline, one feeds $ and X an unlabeled sensing method which operates point by point, returning for every Xj an estimate 8j of x Here one
33
25 45
48
30
32
36
23
may choose to threshold the xj i based on their distance to $ and apply unlaheled sensing on the outliers only. Alternatively, if extra computational power is available for dispensing with choosing threshold, one may apply unlabeled sensing on every Xj; it is this approach that we follow in the rest of the paper. This procedure is summarized in Algorithm
Algorithm 1 Two-stage Algorithmic Pipeline for UPCA
Input: observed data matrix X, rank 2: estimate S of S t- outier-robustt PCA on X
Stage-I >> Stage-II
3: forj= 1,..., TI do
4: estimate R) of x5 t unlabeled sensing on (R),
5: end for
6: return X = =2 [8,,..,, &, estimate of X*
3.2 A new method for unlabeled sensing: Least-Squares with Recursive Filtration (LSRF)
Inasmuch as there are very few scalable unlabeled sensing methods, we here propose a simple but comparatively efficient alternative. Algorithm 2 This method is parameter-free It alternates between ordinary least-squares and a dimensionality reduction step that removes coordinate the ambient space on which the residual error attains its maximal value, until coordinates are left. The number iterations fixed as (m - r), so the overall complexity of Algorithm is 2m We here also mention the time complexity of other unlabeled sensing methods for comparison: AIEM has complexity approximately O(m + r"), PL has complexity at least ((krr)) via second-order optimization, and RRR has complexity at least O(mr² + k(m + r²) )) via sub-gradient descent, where k is the number of iterations.
Algorithm 2 Unlabeled Sensing via Least-Squares with Recursive Filtration (LSRF)
1: Input: permuted point &j. basis B of subspace S*
2: v(0) 8,, (0) - B*
3: for k = -,...., m. - ro
4: C C Ak- (((-1)
5: i' aragmax - (1)
6: remove the i'-th entry v(k-1) to get (k)
7: remove the i' row of A (k-1) get (k)
8: end for
9: return 8, A (m (m-riA (m-r) (m--) estimate for xj
4 Experimental Evaluation
4.1 Robust-PCA with permutation-indueed outliers
We begin by assessing the performance of Stage-I of the pipeline. This entails understanding how different PCA methods with robustness to outliers behave when the outliers are induced by permutations, as in Theorem 3 We consider Self-Expr 45 33 CoP (25). OP 43 and DPCP 37]: 49, we sample S' at random from the Grassmannian Gr(r, m.. Then n points x are sampled random from the intersection of S* with the unit sphere of R to yield X Let nin be the number of inliers X and nout the number of outliers X with Thn + Nout = n. We consider outlier ratios Tww/nn = 0.1 : 0.1 0.9. With fixed Tour T, set IT to the identity for E [nu) and set I7's for j > Tua follows. We consider both dense (a 1) and sparse (a 0.1) permutations. For fixed obtain IIІ
see related work in section I We fix m = 50, n = 500. With dim S -r

---

by randomly choosing om coordinates for each xj and applying a random permutation on those coordinates, As evaluation metric we use the largest among all principal angles between and S* denoted by mmax S). Recall mox , 0 if and only if S*.
Self-Expr
45 35
CoP 25
OP
DPCP 37
40
30
random outliers
20
40
30
= 1.0
20
40
30
= 0.1
0.1 0.3 0.5 0.7 0.9
0.1 0.3 0.5 0.7 0.9
0.1 0.3
0.5 0.7 0.9
0.1 0.3 0.5 0.7 0.9
outlier ratio
Figure 1: max (S+, S) Stage-I: outlier ratio vs. rank phase transitions for various PCA methods with robustness to outliers.
Figure I depicts the outlier-ratio versus rank phase transitions, where to calibrate the analysis with what we know about these methods from prior work, we have included in the top row of the figure the phase transitions for outliers randomly chosen from the unit sphere. By reading that top row we recall: DPCP has overall the best performance across all ranks and all outlier ratios, ii) OP identifies correctly S* only in the low rank low outlier-ratio regime, as expected from its conceptual formulation, and fii) CoP and Self-Expr, even though low-rank methods in spirit, they have accuracy similar to each other and considerably better than OP. We also note that CoP is the fastest method requiring 0.51 sec for the computation 752sec, and DPCP and OP take ss3 and 5.62sec, respectively F
single phase transition plot, Self-Expr is the slowest with
Now let look at what happens for permutation-inde induced outliers. For x= 1, where the permutations move all the coordinates of the points they are corrupting, we see that the phase transition plots are practically the same for random outliers. In other words, obtaining the outliers by randomly permuting all coordinates of inlier points, with different permutations for different outliers, seems, even for low subspace dimensions, to be yielding an outlier set as generic for the task of subspace learning as sampling the outliers randomly from the unit sphere. A second interesting phenomenon observed when the permutation ratio is decreased a 0.1. In that regime the methods exhibit two very different trends. On one hand, CoP and Self-Expr appear to break down, which is expected, because as the permutations become more sparse, the outlier points become more coherent with the rest of the data set. On the other hand, the accuracy of DPCP and OP improves for sparser permutations; justification for this is that both methods get initialized via the SVD of X, which yields a subspace closer to S* for smaller a. An interesting research direction to analyze the theoretical guarantees of these methods for this specific type of outliers.
4.2 UPCA synthetic data
Next, we evaluate the UPCA pipeline of Algorithm I on synthetic data. We keep m = 50 as before,
and add spherical noise corresponding to fixed SNR of 40dB, We get the estimate Š of S* via DPCP and Algorithm 2 Stage-II get & from and X. We distinguish between dense and sparse permutations.
37 in Stage-I and apply the unlabeled sensing methods 36 23 30 32]
Experiments
Intel(R) 17-8700K, 3.7 GHz, 16GB machine.
7

---

UPCA with dense permutations (a 1). Figure depicts the relative estimation error of for different outlier ratios from 75% (25 inliers) 94% inliers) and ranks T 3, 4, To assess the overall effect of the quality of S, we use two versions of AIEM and CCV-Min. The first, denoted by AIEM(S) and CCV-Min(S), uses as input the estimated subspace S, while the second version, AIEM(S") and CCV-Min(S*), uses the ground-truth subspace S Note that the estimation error of AIEM(S /CCV-Min(S")) is independent of the outlier ratio. On the other hand, the estimation error of (1EM(SyCCVMMig)
depends on the outlier ratio through the computation of S. Indeed, is expected to be closer to S* for smaller outlier ratios, as we already know from Figure L In particular, for up to 75% outliers the estimation error of A CCV-Min(S) coincides with that of AIEM(S*)) CCV-Min(S"). indicating an accurate estimation of S At the other extreme, for 94% outliers both / CCV-Min(S) break down, indicating that the estimation of $ failed. Finally, note that CCV-Min has at least half order of magnitude smaller estimation error than AIEM. This is due our specific choice of the tranch-&-bount CCV-Min parameters which control the trade-off between accuracy and running time; for example, for r = 3 and 75% outliers, AIEM runs in 0.042sec with 1 error, while CCV-Min needs about 15sec to bound & 0.42% away from X*
AIEM(S)
OCV-Min(S)
ATEM(S")
|8-X" In
0.1
CCV-Min(S")
0.1
0.01
0.01
0.01
75%
80%
85
90%
94%
75%
80%
85%6
90%
94%
75%
80%8
85%
90%
94%
outlier ratio
outlier ratio
outlier ratio
(a) r
3
(b) r =
(c) r == 5
Figure 2: UPCA (Algorithm 1b for dense permutations (a = 1) with S produced by DPCP 37 at
Stage-T and & produced by AIEM 36 or CCV-Min 23 at Stage-II.
show the relative estimation error of UPCA for a = 0.1 0.1 0.6, rank r = 1 25, and outlier ratio fixed to 90%. with $ computed in Stage-I by DPCP (37) and & comppued via & RRRR 30
UPCA with sparse permutations (a < 0.6). Figures 3b 3d
PL [32] or Algorithm 2 from X and S in 25 m/2 2 is the largest rank for which unique recovery of
Stage-II. is important to note that
24 Figure Ba shows that 0 (S+ S) always stays below 2", indicating the success of DPCP. Now ł RRR and AlgorithmmIiann havee similar accuracy, but Algorithm is more efficient than -RR, considering that computing X takes 0.3sec for Algorithm and 1.5min for RRR. Even though PL delivers & in seec it not performing as well, which we attribute its sensitivity the particular basis of S* that is used to generate the data; this is available here since DPCP returns the specific basis of dual principal components.
X is theoretically possible 38 39
34
35
10
25
0.3
25
25
25
19
19
19
1F 13
13
13
0.1
7
0"
2 3
3 4 5 66
.1.2
2 4
5
(a) 0
(b) R 30
PL
(d) Algorithm
Figure 3: Estimation error - of UPCA (Algorithm for sparse permutations (a 0.6) and
outlier ratio 90%, with computed by DPCP 37 in Stage-T and & computed by 2-RR 30 PL 32 or Algorithm 2 in Stage-II.

---

4.3 UPCA on face images
In this section we offer flavor how the ideas discussed far apply in eigh-dimensional example with real data. We use the well-known database Extended Yale B [14], which contains fixed-pose -ose face images of distinct individuals, with 64 images per individual under different illumination conditions. It is well-established that the images of each individual approximately span low-dimensional subspace. turns out that for our purpose the value dim S 4 is good enough. Since each image has size 192 x 168, the images of each individual can be approximately seen as 64 points x E [64] of 4-dimensional linear subspace S", embedded in an ambient space of dimension m 32256. In what follows we only deal with the images of a fixed individual. We consider four permutation types corresponding to fully or partially (a 0.4) permuting image patches of size 16 24 48 42, as shown in the second column of Figure 4 To generate fixed number of Nout 16 outliers, only one out of the four permutation types is used for each trial. The original images (inliers) together with the ones that have undergone patch-permutatinn
(outliers) are given without any inlier/outlier labels, and the task is to restore all corrupted images. This is special case of visual permutation learning, recently considered using deep networks [26 27
original
outlier
AIEM 36
- 30
32
Algorithm
Figure 4: UPCA the face dataset Extended Yale B.
The first column of Figure shows an original image, and the second column shows the corresponding outlier obtained by applying a sample permutation for each of the four different permutation types. Columns three to six give the corresponding point in the output of Algorithm for different unlabeled sensing methods and Š computed by DPCP (37) (CCV-Min (23 is not included as branch-&-bourd becomes prohibitively expensive for such large m.. Notably, AIEM (36) rather satisfactorily restores the original image regardless of permutation type. The performance of the other three methods is shown only for their operational regime of sparse permutations, and Algorithm 2 most accurately captures the illumination of the original image. Overall, we find these results encouraging, especially one takes into consideration that the methods are very efficient, requiring only 0.2sec (AIEM), 7sec (c₁ (RR,, 0.2sec (PL) and 10sec (Algorithm 2). discounting the DPCP step, which costs O. secc regardless of permutation type. This is in contrast with existing deep network architectures for visual permutation learning, such as (27]. which are based on branch-& --buund and thus have in principle an exponential complexity the number permuted patches.
4.4
UPCA on data re-identification
Finally, we evaluate the UPCA Algorithm [ for the task of data re-identification (see section using real educational and medical records and simulated permutations for various sparsity levels &. thus emulating a privacy protection scenario. Both of the datasets that we use contain no personally
identifiable information. DPCP (37 computes $ in Stage-l, and RR 30 PL 32 or Algorithm produces X in Stage-II.
The first dataset consists of the test scores of m 707 high-school students 6 subjects during two different periods, together with the sum of the score tests for each period, thus n = 14. For out of 14 tests, we apply random permutations of the student indices and thus have 50% outliers. With r r= 3, the relative estimation errors on the score records are shown in Figure 5a The black dashed line depicts the relative difference between the observed data X and the original data X", which as expected increases for higher a's. s. Since e -RR, PL, and Algorithm 2 are by design suitable for sparse

---

0.2
0.4
1R-x"11 lle
0.15
0.3
PL [30]
||-|||
T 4 [28]
0.2
Algorithu 2
0.1
0.1
0.05
0.4
0.4
OF
(a) high-school scores
(b) breast tumor features
Figure 5: Relative estimation error on real data in de-anonymization.
permutations, their performance naturally degrades for large a. But up to 0.7 aligns with our earlier findings in that Algorithm tends to have superior performance on the average, and we also see that in that regime also has the smallest variance.
The second dataset consists of all the benign cases in Breast Cancer Wisconsin (Diagnostic) 12 has m 357 patients and = features of breast mass digitized image for each patient. We randomly permute the patient indices for 15 of the features thus having 50% outliers and set = 4. Figure 5b shows the relative estimation еrror of & for various permutation sparsity levels x. with the unlabeled sensing methods exhibiting the same trend before. Remarkably, for 0.7, the
UPCA Algorithm iinorpporating Algorithm 2 in Stage-Il reduces the original error of the data X from 32. 32.24% to 6.35% % 0.5sec, as opposed to 15.90% and 19.57% when R 330 or PL. 332 incorporated, respectively.
Discussion
Some interesting conclusions be drawn from this work regarding privacy protection. First, appears to be not secure for data providers to only partially permute the data, since, as we have seen, permuting only subset of the features enables re-identification. Re-identification is also possible if a database is fully permuted but another uncorrupted database with the same subjects is accessible or present an assembled dataset. On the other hand, arbitrary dense permutations are extremely difficult to recover, as one would need to solve an intractable polynomial system.
A related interesting direction for future research is the where top of permutations one has missing entries, a problem that we term unlabeled matrix completion. The missing entries, may either arise naturally, since for example not all same subjects common across databases, but they could also serve as part of a privacy protection protocol. [44] discusses the algebraic structure of unlabeled matrix completion and gives results regarding finite recovery.
Acknowledgement
This work funded by ShanghaiTech start-up grant 2017F0203-000--6.
References
[1] A. Abid, J. Zou. stochastic pnpectation-maximinn approach to shuffled linear regression. In Annual Allerton Conference Communication, Control, and Computing (Allerton). 201 88
[2] M. Abowd. Stepping-up: The census bureau tries to good data steward the 21 century. 2019.
[3] M. Antoni, R. Schnell. The past, present and future of the german record linkage center. Jahrbücher für Nationalökonomie und Statistik, 239(2):319 331, 2019.
10

---

[4] D. Bertsimas, M. L. Li. Fast exact matrix completion: A unified optimization framework for matrix completion. Journal of Machine Learning Research, 21(231):1 2020.
[5] F. Brown, J. Cocke, S. A. Della Pietra, V. J. Della Pietra, F. Jelinek, J. D. Lafferty, Mercer, P. S. Roossin. statistical approach to machine translation. Computational Linguistics, 16(2):79-88) 85, 1990.
[6] E. J. Candès, X. Li, Y. Ma, J. Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
[7] E. J. Candès, B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 96))7177-77,, 2009.
[8] D. Cox, J. Little, D. OShea. Ideals, Varieties, and Algorithms: Introduction Computational Algebraic Geometry and Commutative Algebra. Springer Science & Business Media, 2013.
[9] T. Ding, Z. Zhu, R. Vidal, D. P. Robinson. Dual principal component pursuit for robust subspace learning: Theory and algorithms for holistic approach. In International Conference on Machine Learning, 2021.
[10] Dokmanic. Letters, 26(6):823-88) 807,827.222 2019.
Permutations unlabeled beyond sampling unknown. IEEE Signal Processing
[11] J. Domingo-Ferie Ferrer, K. Muralidhar. New directions in anonymization: Permutation paradigm, verifiability by subjects and intruders, transparency to users. Information Sciences, 337-338:1 24, 2016.
[12] D. Dua, C. Graff. UCI machine learning repository, 2017.
[13] I. P. Fellegi, A. B. Sunter. theory for record linkage. Journal of the American Statistical Association, 64(328): 118--121111111 1969.
[14] A. S. Georghiades, N. Belhumeur, D. Kriegman. From few many: Illuiinaioon cone models for face recognition under variable lighting and pose. IEEE Transactions on Pattern Analysis and Machine Intellignce, 23(6):643-660, 2001.
[15] J. Harris. Algebraic Geometry: A First Course, volume 133, Springer Science Business Media, 1992.
[16] X. He, Y. Xiao, Li, Q. Wang, W. Wang. Shi. Permutation anonymization: Improving anatomy for privacy preservation in data publication. In PAKDD Workshops, 2011.
[17] D. Hsu, K. Shi, X. Sun. Linear regression without correspondence. In Advances in Neural Information Processing Systems, 2017.
[18] G. Lerman, T. Maunu. Fast, robust and non-convex subspace recovery. Information and Inference: A Journal of the IMA, 7(2):277-336, 2018.
[19] Marano, Willett. Making decisions by unlabeled bits. IEEE Transactions on Signal Processing, 68:2935-2947, 2020.
[20] K. Muralidhar. Record re-identification of swapped numerical microdata. Journal Information Privacy and Security, 13(1):34-45, 2017.
[21] A. Nejatbakhsh, E. Varol. Neuron matching in elegans with robust approximate linear regression without correspondence. In IEEF/CVF Winter Conference on Applications of Computer Vision, 2021.
[22] A. Pananjady, J. Wainwright, T. A. Courtade. Linear regression with shuffled data: Statistical and computational limits of permutation recovery. IEEE Transactions on Information Theory, 64155):226-3300, 2017.
[23] I.. Peng. M. C. Tsakiris. Linear regression without correspondences via concave minimization. IEEE Signal Processing Letters, 27:1580-1584, 2020.

---

[24] L. Peng, M. C. Tsakiris. Homomorphic sensing of subspace arrangements. Applied and Computational Harmonic Analysis. 55:466-485, 2021.
[25] M. Rahmani, G. K. Atia. Coherence pursuit: Fast, simple, and robust principal component analysis. IEEE Transactions on Signal Processing, 65(23):6260- (252))6666-677,, 2017.
[26] R. Santa Cruz, B. Fernando, A. Cherian, S. Gould. Deeppermnet: Visual permutation learning. In IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[27] R. Santa Cruz, B. Fernando, A. Cherian, S. Gould. Visual permutation learning. /EEE Transactions Pattern Analysis and Machine Intelligence, 41(12)3100-3114 2019.
[28] A. Schmaltz, A. M. Rush, S. Shieber. Word ordering without syntax. In Conference on Empirical Methods in Natural Language Processing, 2016.
[29] T. Shen, Lei, R. Barzilay, T. Jaakkola. Style transfer from non-parallel text by cross-alignment. In Advances in Neural Information Processing Systems, 2017.
[30] M. Slawski, E. Ben-David. Linear regression with sparsely permuted data. Electronic Journal of Statistics, 13(1):1-36, 2019.
[31] M. Slawski, Ben-David, P. Li. Two-stage approach to multivariate linear regression with sparsely mismatched data. Journal of Machine Learning Research, 22(44) 1200)):-42, 2020.
[32] M. Slawski, G. Diao, E. Ben-David. A pseudo-likelihood approach to linear regression with partially shuffled data. Journal of Computational and Graphical Statistics, 0(0):1-31, 2021. 2021.
[33] M. Soltanolkotabi, E. J. Candes. geometric analysis of subspace clustering with outliers. The Annals of Statisties, 40(4):2195-231) 22388, 2012.
[34] M. C. Tsakiris.
Determinantal conditions for homomorphic sensing.
preprint
2018
[35] M. C. Tsakiris, L. Peng. Homomorphic sensing. In International Conference Machine Learning, 2019.
(36) M. C. Tsakiris, I.. Peng, A. Conca, I.. Kneip, Y. Shi, H. Choi. An algebraic-geometric approach for linear regression without correspondences. IEEE Transactions on Information Theory, 66(8):5130-5144, 2020.
[37] M. C. Tsakiris, R. Vidal. Dual principal component pursuit. The Journal of Machine Learning Research, (9(1):684-332 2018.
[38] Unnikrishnan, S. Haghighatshoar, M. Vetterli. Unlabeled sensing: Solving linear system with unordered measurements. In Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2015.
[39] J. Unnikrishnan, S. Haghighatshoar, M. Vetterli. Unlabeled sensing with random linear mea- surements. IEEE Transactions on Information Theory, 64(5):3237-3253, 2018.
[40] N. Vaswani, T. Bouwmans, S. Javed, P. Narayanamurthy. Robust subspace learning: Robust pea, robust subspace tracking, and robust subspace recovery. IEEE Signal Processing Magazine, 35(4):22-55, 2018
[41] G. Wang, S. Marano, J. Zhu, Z. Xu. Target localization by unlabeled range measurements. IEEE Transactions on Signal Processing, 68:6607-6620, 2020.
[42] Y. Xie, Y. Mao, S. Zuo, H. Xu. X. Ye, T. Zhao, H. Zha. A hypergradient approach to robust regression without correspondence. International Conference on Learning Representations, 2021.
[43] H. Xu, C. Caramanis, S. Sanghavi. Robust pea via outlier pursuit. IEFE Transuctions on Information Theory, 58(5):3047-3044, 2012.
12

---

[44] Y. Yao, L. Peng, M. C. Tsakiris. Unlabeled principal component analysis. arXiv preprint arXiv:2101.09446, 2021.
[45] C. You, D. Robinson, Vidal. Provable self-representatioon based outlier detection in a union of subspaces. In IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[46] H. Zhang, P. Li. Optimal estimator for unlabeled linear regression. In International Conference on Machine Learning, 2020.
[47] T. Zhang, Y. Yang. Robust pea by manifold optimization. Journal of Machine Learning Research, 101-333,,,,,,, 2018.
[48] Z. Zhu, Y. Wang, D. P. Robinson, D. Naiman, R. Vidal, M. C. Tsakiris. Dual principal component pursuit: Improved analysis and efficient algorithms. In Advances in Neural Information Processing Systems, 2018.
13


Reviews:
[{"review_id": "v9HKO2zsBUQ", "reviewer": "Reviewer_azUW", "summary": "The paper introduced a variant of PCA in the presence of noise, i.e., a variant of robust PCA. The \"noise\" in this case is permutations of the column entries of the data matrix. Using concept from Algebraic geometry, the authors showed that they can get the solution upto permutation of the rows. Experimental results have shown that the proposed method can recover the data matrix under such corruption.", "questions": "", "limitations": "", "rating": 8, "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": "This is an excellent paper in terms of theoretical contribution. In my knowledge, this is the first paper which uses algebraic geometry to have a polynomial solution of robust PCA where the noise if permutation of column entries. \n\nStrength:\n(a) Theorem 3 is very interesting as it shows that the corrupted data matrix admits a partition into a inlier and outlier based on the ground truth column space. This is the main finding that helps to give the two stage proposed algorithm\n(b) The polynomial two stage algorithm is natural as in the first stage the authors tried to find an estimation of column space. Given an estimation of the column space, using Theorem 3 the authors used a sensing method as second stage to get the partition between inliers and outliers.\n\nMy main criticism is readability of the paper, please see the comments below\n(a) The paper is very dense in places and even with a fair knowledge about algebraic geometry the reader may find it difficult to read, e.g., (i) the authors should separate definition/discussion about Zariski topology in separate paragraph, line 115 - 132 can be  restructured (ii) Theorem 3 should be introduced before and theorem 1 and 2 may be discussed in detail in supp. material (iii) The discussion regarding polynomial root finding starting from line 150 is dense and can be restructured. (iv) The authors did not spend enough lines explaining the polynomial algorithm, for example complexity analysis of Algorithm 2 needs to be there.\n\n(b) The experimental results should be cut down as the main contribution is Theorem 3 and the polynomial algorithm. \n\nI am willing to strong accept after this restructuring for better readability. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "h0Dn2V1_-lv", "reviewer": "Reviewer_Xvq6", "summary": "- The authors describe and tackle the problem of unlabelled principal component analysis, a variant of PCA where the columns of the data matrix might have been permuted arbitrarily with different permutations for each column. The problem shares some of its motivation with the easier problem of unlabelled sensing, where the principal subspace is known.\n- The authors divide the problem of UPCA into two natural steps: i) Identifying a rank-r subspace S* where all data points lie if permitted correctly, and; ii) mappings the permuted data points onto the identified subspace. These two steps can be naturally addressed by existing lines of work: robust PCA for former and unlabelled sensing for the latter.\n- The authors use a algebraic framework to formulate and solve the problem. The main theoretical result is a powerful one: under genericity of the true solution, then any solution of the rank minimization formulation of the problem recovers the ground truth up to a permutation.\n- A combinatorial solution is prohibitively expensive. One could consider a polynomial system solver, but the authors correctly point out that scalability and robustness to noise would pose separate challenges and leave that to future work. \n- Instead, the authors focus on specific subclasses of the UPCA problem where only a fraction of the entries are permuted. Under this assumption it is indeed possible to have efficient solutions of the problem, and the proposed two-stage workflow seems well suited.\n- Finally, the authors provide extensive experiments on their methodology on synthetic and real datasets. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "I recommend acceptance for the paper. In my opinion it is clearly above the bar in all respects. The problem is convincingly useful, challenging and not really studied so far. The authors put a lot of effort providing not just the raw technical results but also very helpful pedagogical discussion that makes this mathy paper more easily accessible to the ML folk. \n\nStrong points: \n1. Motivation: This line of work and this problem in particular is relatively new and not necessarily widely recognized as important. So it was important for the authors to provide convincing motivation. I was happy to see that the introduction provides a solid, clear motivation for the problem with plenty of references.\n2. Technically the paper is solid. The authors use unusually heavy algebra to prove their main result, but Section 2 provides a concise, but pedagogical explanation of the algebraic results necessary in the paper. \n3. The evaluation is relatively extensive and more than sufficiently thorough. I appreciated the effort that the authors put in evaluating different base methods for the two “stages” for their UPCA workflow. \n\nWeak points and questions: \n1. With the exception of the proposal of Algorithm 2 (an alternative method for unlabelled sensing) the methodology in the paper is completely drawn from the robust PCA and unlabelled sensing literature. I mention this point for completeness, but I think that it is a minor point that does not detract from the paper’s value. The strong points mentioned above outweigh this point.\n2. Algorithm 2 seems to perform great on the re-identification problem of Section 4.4. On the other hand, it doesn’t seem particularly useful in the face experiments of 4.3 (AIEM appears to be both faster and more accurate that Algorithm 2  in the experiment of Figure 4). Can the authors comment a bit on what might be the best conditions to use Algorithm 2 vs AIEM?\n3. There is discussion in the main body of the paper on what it means for a solution to be generic in algebraic terms. Can the authors provide some discussion on a few reasonable necessary or sufficient conditions for data matrices to be generic in applications?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention some positive aspects when it comes to societal impact, but I feel like there’s an important point missing: \n- Is it not true that powerful de-anonymization methodology can be used to violate the privacy of certain data releases? That sounds potentially harmful, so it might be useful to give it some thought and add a bit of discussion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ftOZlnj5PB3", "reviewer": "Reviewer_9vKy", "summary": "This paper introduces unlabeled principal component analysis (UPCA), which refers to the reconstruction of the ground-truth data matrix X^* from its unlabeled version \\tilde{X}, whose each column is generated from a permutation of the coordinates of the corresponding column of X^*. The authors first establish that UPCA is well-posed by showing that if X^* is sufficiently \"generic\", then the solution to the UPCA presented in Eq. (2) applied to \\tilde{X} is X^* (up to a global permutation matrix). The authors then establish that X^* (up to a global permutation matrix) is the unique solution of a polynomial system of equations parametrized by \\tilde{X}. Based on these theoretical results, the authors propose a two-stage algorithmic pipeline for UPCA for a practically relevant case where only a fraction of the data has been permuted. The first stage uses robust PCA methods to estimate \\hat{S} of the ground-truth column space S^* from \\tilde{X}. The second stage uses unlabeled sensing methods to estimate \\hat{X} of the ground-truth data matrix X^* from \\hat{S} and \\tilde{X}. The authors also introduce a novel algorithm for unlabeled sensing based on least-squares with recursive filtration (LSRF).", "questions": "", "limitations": "", "rating": 6, "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": "Overall, I think the introduced UPCA problem is interesting with both theoretical guarantees provided in Theorems 1 to 3 and potential practical applications as demonstrated in Section 4, and the technical results seem to be correct (but I have not checked the proofs in detail). Some comments:\n\n1) The notion \"generic\" is important for the theorems and the authors should present a Definition 1 to provide a clear and concise definition of it. They should refer to Definition 1 when \"generic\" first appears in Line 45 on Page 2. \n\n2) The authors should present the Output of Algorithms 1 and 2 clearly. \n\n3) In Figures 3 and 4, Algorithm 2 can be abbreviated as LSRF, and the authors do not need to present the reference for each algorithm in all the figures. \n\n4) Currently, from the experimental section, I cannot see the benefit of introducing Algorithm 2 (LSRF) clearly. I guess the major advantage of LSRF is its efficiency. But the authors only mention that it is fast for a single case corresponding to Figure 3. For a case corresponding to Figure 4, it is even the slowest algorithm (takes 10 seconds, as mentioned in Line 288). To show LSRF is more efficient than other unlabeled sensing methods to compare, the authors should present the time complexity of all these methods clearly (and perhaps the parameter regimes where these methods work) and present tables comparing the running time of these methods for many cases. \n\n5) Some notational issues: Line 34, revise \\tilde{x}_1 \\in \\mathbb{R}^m, \\ldots, \\tilde{x}_n  \\in \\mathbb{R}^m to \\tilde{x}_1, \\ldots, \\tilde{x}_n  \\in \\mathbb{R}^m; Line 35, revise ith row to $i$-th row. Line 98, it is weird to write S^* = C(X^*) without any definition of C. Line 250, avoid using msec. Lines 258 and 289, avoid using 0.3sec seconds and 10sec seconds. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the limitations and potential negative societal impact of this work have been addressed in the Checklist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "bSZHKB4GChM", "reviewer": "Reviewer_8z2R", "summary": "The paper aims to recover a low-rank matrix in which the entries of the columns are permuted. The paper first provided theoretical analysis to show the feasibility of the recovery problem and then proposed a two-step method with a modified unlabeled sensing algorithm. The numerical results on synthetic data, face images, and other two datasets showed that the proposed two-step method is quite effective and the modified unlabeled sensing algorithm can outperform existing algorithms in most cases.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "In the proposed method, the first step is to perform robust PCA on the permuted data matrix to find an estimation of the subspace.  The second step is to use the estimated subspace basis to perform unlabeled sensing to recover the matrix.  The author investigated the performance of four RPCA algorithms and four unlabeled sensing algorithms including the one proposed in the paper. In general, the paper consists of theory, practical algorithm, and real applications. The paper is well-written and the idea is quite interesting and novel.  Nevertheless, there are a few limitations.\n\n1. It seems that there is a big \"gap\" between Section 2 and Section 3. The proposed algorithm does not consider or take advantage of any information in Theorem 2/3. Therefore, the significance of Theorem 2/3 is not big. \n\n2. It is surprising that in Figure 1 DPCP works well when the rank is 48 or 49. In these cases, the matrix X is almost full-rank. \n\n3. In Figure 4, why did Algorithm 2 fail in the first two cases? The performance is quite different from that in Section 4.4.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors identified an interesting problem about principal component analysis with unknown permutations of the feature in each data sample. They then proposed an algorithm and provided performance guarantee. All 4 reviewers agreed to accept this paper.

Decision: Accept (Poster)