Unlabeled Principal Component Analysis
Year: 2021

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.

heading: 1 Introduction

heading: 1.1 Motivation
text: In principal component analysis, a cornerstone of machine learning and data science, one is given a data matrix X̃, assumed to be a corrupted version of a ground-truth data matrix X∗ = [x∗1 · · · x∗n] ∈ Rm×n, typically but not necessarily assumed to have low rank, and the objective is to estimate X∗ or the column-space S∗ ⊂ Rm of X∗. The most common types of corruptions that have attracted interest in modern studies are 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 [7, 4].
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 or even are entirely unavailable [38, 39, 22, 17, 30, 31, 46, 19, 41, 36]. There, one is given a point x∗ of a linear subspace S∗, but only up to a permutation of its coordinates, say x̃ = Π∗x∗ with Π∗ an unknown permutation, and the goal is to find x∗ from the data x̃, S∗. This Unlabeled Sensing [38, 39] problem has many potential machine learning applications, e.g., record linkage [30, 31], visual [26, 27] or textual [5, 28, 29] permutation learning, and matching problems in neuroscience [21] and biology [1, 42].
While methods for unlabeled sensing rely on knowledge of the source subspace S∗, this is not always known in practice. On the other hand, data of the form X̃ = [x̃1, . . . , x̃n] ∈ Rm×n with x̃j = Π∗jx∗j an unknown permutation of an unknown point x∗j ∈ S∗, are often available, thus raising the question of whether S∗ can be estimated from X̃. An important example of this situation is record linkage [13, 20, 3], where the objective is to integrate data from independent sources, x̃1, . . . , x̃n ∈ Rm, for subsequent data analysis. Since the entries of different records x̃i’s are collected separately, the data matrix X̃ is unlabeled in the sense that, the entries of its i-th row do not necessarily correspond
35th Conference on Neural Information Processing Systems (NeurIPS 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 [11, 16]. 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 a balance between data privacy and data preservation, the subject of a plenary talk in the 2019 International Conference on Machine Learning [2].

heading: 1.2 Contributions
text: 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 r := rank(X∗) < min{m,n} and X∗ is generic (see Definition 1), then up to a permutation of its rows, X∗ is the only matrix of rank less than or equal to r that is compatible with X̃. This asserts that UPCA is a well-posed problem, since the inherent ambiguity of whether X̃ comes from X∗ or a row-permuted version of X∗ is in most cases practically harmless.
• We establish that in this basic formulation UPCA is a purely algebraic problem, by exhibiting a polynomial system of equations parametrized by X̃, whose solutions are all the rowpermutations 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 a 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 to one of the records having much larger size than the others. The first stage of the pipeline employs PCA methods with robustness to outliers [43, 33, 25, 45, 37, 48, 18] to produce an estimate Ŝ of S∗ from X̃; the second stage of the pipeline uses unlabeled sensing methods [30, 32, 36, 23] to furnish an estimate X̂ of X∗ from Ŝ 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.

heading: 1.3 Related work
text: Unlabeled sensing. There is a large literature on application-specific problems that involve lack of correspondences, e.g. in computer vision or 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∗ ⊂ Rm of dimension r and a point x̃ which is some permuted version of a point x∗ ∈ 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 (α = 1) is extremely challenging, with existing methods only able to handle small ranks r. We consider two methods known to perform best in this regime. The first one is the algebraic-geometric AIEM method of [36]. This has linear complexity in m and instead concentrates its effort on solving a polynomial system of r equations in r variables to produce an initialization for an expectation maximization algorithm. Currently, this method is efficient for r ≤ 5 and intractable otherwise. A very different method is CCV-Min of [23], which proceeds via branch-&-bound together with concave minimization and can handle ranks r ≤ 8. For sparse permutations (small α) dealing with higher ranks becomes possible [30, 32]. The `1-RR algorithm of [30] applies an `1 robust linear regression relaxation, and it works when α ≤ 0.5. Another approach is the Pseudo-Likelihood method (PL) of [32], which fits a 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, PL can tolerate up to α = 0.7 but it is sensitive to the particular basis of S∗ used to generate x̃.
Robust PCA with outliers. PCA methods with robustness to outliers will also play a 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∗ ⊂ Rm and outlier points that lie away from S∗, and the goal is to recover S∗ from X̃. The Outlier Pursuit (OP) method of [43] decomposes X̃ via convex optimization into the sum of low-rank and column-sparse parts. The convex method of [45], a successor of [33], referred to as Self-Expr, solves a self-expressive elastic net problem so that each x̃j is expressed as an `2-regularized 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 as a score for inliers vs. outliers, with higher scores expected for the former. The Coherence Pursuit (CoP) method of [25] is based on the following simple but effective principle: with X̃−j the matrix X̃ with column j removed, for each x̃j one computes its coherence X̃>−jx̃j with the rest of the points. As it turns out, inliers tend to have coherences of higher `2-norm than outliers, and the top r x̃j’s are taken to span Ŝ. Finally, the Dual Principal Component Pursuit (DPCP) of [37] solves an `1 non-smooth problem on the Grassmannian via iterated-reweighed 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, 9] to tolerate as many outliers as the square of the number of inliers.

heading: 2 Theoretical Foundations

heading: 2.1 Problem Formulation
text: Let us denote by Pm the set of all permutations of coordinates of Rm. We let X∗ = [x∗1 · · · x∗n] ∈ Rm×n 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̃ = [x̃1 · · · x̃n] = [Π∗1x∗1 · · ·Π∗nx∗n] ∈ Rm×n, (1) where each Π∗j ∈ Pm is an unknown permutation. Let Pnm = ∏ i∈[n] Pm be n ordered copies of Pm, where [n] = {1, . . . , n}. For π = (Π1, . . . , Πn) ∈ Pnm we set π(X̃) = [Π1x̃1 · · ·Πnx̃n]. We pose Unlabeled Principal Component Analysis (UPCA) as the following rank minimization problem:
min π∈Pnm rankπ(X̃) (2)
First, note that (2) never has a unique solution, because if π = (Π1, . . . , Πn) is a solution, then so is π ′ = (ΠΠ1, . . . , ΠΠn), where Π ∈ Pm is any permutation. This reveals an inherent ambiguity of UPCA: it is only possible to recover X∗ from X̃ up to a permutation ΠX∗ of its rows. On the other hand, this is rather harmless in many situations, since ΠX∗ is the same dataset as X∗ except that the row-features appear now in some different order. Thus, our hope in formulating (2) is that the only solutions are of the form π = (ΠΠ∗1 >, . . . , ΠΠ∗n >) with Π ranging across Pm and Π∗j as in (1). However, without any other assumptions on the data X∗, there could in principle be additional undesired permutations that also give rankX∗, or even worse, the minimum rank in (2) could be lower than r = rankX∗. Our results show that for generic enough data, such pathological situations do not occur, and the only solutions to (2) are the ones associated with row-permutations of X∗.

heading: 2.2 Elements of Algebraic Geometry
text: Before stating our results, we make the notion of generic precise using some basic algebraic geometry [8, 15]. Let Z = (zij) be an m× n matrix of variables zij and R[Z] = R [ zij : i ∈ [m], j ∈ [n] ] the ring of polynomials in the zij’s with real coefficients. An algebraic variety of Rm×n is the set of solutions of a polynomial system of equations in R[Z]. In particular, the set of (r + 1) × (r + 1) determinants of Z are polynomials in zij’s of degree r+ 1 and define the algebraic variety
Mr = {X ∈ Rm×n| rankX ≤ r } , since a matrix X ∈ Rm×n has rank at most r if and only if all (r+ 1)× (r+ 1) determinants of X are zero.
The algebraic varietyMr admits a topology, called Zariski topology, which makes it convenient to work with. The closed sets in this topology are the algebraic subvarieties of Mr. These are sets of matrices of rank ≤ r, which in addition satisfy certain other polynomial equations in R[Z]. For example, the set of matrices of rank at most r− 1 is a proper closed subset ofMr, because in addition to the equations definingMr, it is further defined by requiring all r× r determinants to be zero. Open sets inMr 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 r is a proper open subset ofMr defined by the non-simultaneous vanishing of all r × r determinants of Z; a matrix has rank r if and only if all (r + 1) × (r + 1) determinants are zero and least one r× r determinant is non-zero. Now, the algebraic varietyMr is irreducible in the sense that it can not be described as the union of two proper algebraic subvarieties of it. A consequence of this is that non-empty open sets ofMr have the very important property of being topologically dense. This means that given a non-empty open set U ⊂ Mr and a point X ∈Mr, every neighborhood of X intersects U . It follows that under any non-degenerate continuous probability measure onMr, a non-empty Zariski-open set ofMr has measure 1. For example, the set of matrices inMr of rank r is non-empty and open, and thus it is dense. Hence a randomly sampled matrix inMr under a continuous probability measure will have rank r with probability 1. We refer to such a fact by saying that a generic matrix inMr has rank r. More generally: Definition 1. We say that a generic matrix inMr satisfies a property, if the property is true for every matrix in a non-empty open subset ofMr.

heading: 2.3 UPCA is a Well-Posed Problem
text: Our main theoretical result is1:
Theorem 1. For X∗ a generic matrix inMr, we have that rankπ(X̃) ≥ r for any π ∈ Pnm, with equality if and only if π(X̃) = ΠX∗ for some Π ∈ Pm.
Theorem 1 says that for X∗ ∈Mr generic, and up to a permutation of the coordinates of Rm, S∗ is the unique r-dimensional subspace that explains the data X̃ in the UPCA sense, and r = rankX∗ is the minimum objective in (2).

heading: 2.4 UPCA is an Algebraic Problem
text: How can one go about solving the discrete optimization problem (2)? In general, brute force selection of the Πj’s has complexity O ( (m!)n ) , which is out of the question. On the other hand, problem (2) has a rich algebraic structure, which we harvest by showing that X∗, up to a permutation of its rows, arises as the unique solution to a polynomial system of equations.
To begin with, for each j ∈ [n] and each ` ∈ [m], we define the following column-symmetric polynomials of R[Z]:
p̄`,j(Z) := ∑ i∈[m] z`ij
p`,j(Z) := p̄`,j(Z) − p̄`,j(X̃) Note that p̄`,j ( π(Z) ) = p̄`,j(Z) for any π ∈ Pnm and thus p̄`,j(X̃) = p̄`,j(X∗). Now let us think of X ∈Mr as a product of two matrices of sizem× r and r× n, and let us define another polynomial ring with variables associated to these two factors. For i = r+ 1, . . . ,m, and k ∈ [r] and j ∈ [n], we let bik, ckj be a new set of variables over R. Organize the bik’s to occupy the (m− r)× r bottom block of anm× r matrix B whose top r× r block is the identity matrix of size r, and the ckj’s into a k× n matrix C = (ckj). For i ∈ [m], we write b>i for the i-th row of B; for j ∈ [n], we write cj for the j-th column of C. With x̃ij, x∗ij the i-th coordinate of x̃j, x ∗ j respectively, we obtain polynomials
q`,j for ` ∈ [m], j ∈ [n] of R[B,C] by substituting zij 7→ b>i cj in the p`,j(Z)’s above: q`,j(B,C) := p̄`,j(BC) − p̄`,j(X̃) =
∑ i∈[m] (b>i cj) ` − ∑ i∈[m] x̃`ij = ∑ i∈[m] (b>i cj) ` − ∑ i∈[m] x∗ij `
1The proofs of Theorems 1-3 can be found in [44].
The set of common roots of all q`,j’s defines an algebraic variety that depends only on X∗, given by YX∗ := { (B ′, C ′) ∈ Rm×r × Rr×n |q`,j(B ′, C ′) = 0, ∀` ∈ [m], ∀j ∈ [n]; B ′[r],[r] = Ir } ,
where B ′[r],[r] = Ir signifies that the top r× r block of B ′ ∈ Rm×r is the identity matrix. Let us get a feeling about the points of YX∗ . With Π ∈ Pm, if the column-space C(ΠX∗) of ΠX∗ does not drop dimension upon projection onto the first r coordinates, then there exists a unique basis B∗Π of C(ΠX∗) with the identity matrix occurring at the top r× r block. In that case, there is a unique factorization ΠX∗ = B∗ΠC ∗ Π and the point (B ∗ Π, C ∗ Π) lies in the variety YX∗ because
q`,j(B ∗ Π, C ∗ Π) = p̄`,j(B ∗ ΠC ∗ Π) − p̄`,j(X̃) = p̄`,j(ΠX ∗) − p̄`,j(X ∗) = p̄`,j(X ∗) − p̄`,j(X ∗) = 0.
Our second result says that if X∗ is generic, then all points of YX∗ are of this type. That is, they correspond to factorizations B∗ΠC ∗ Π of ΠX
∗ as Π varies across all permutations: Theorem 2. For a generic matrix X∗ inMr we have
YX∗ = { (B∗Π, C ∗ Π) ∈ Rm×r × Rr×n |Π ∈ Pm; B∗Π,[r],[r] = Ir; ΠX ∗ = B∗ΠC ∗ Π } .
Thanks to Theorem 2 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
q`,j(B,C) = 0, ∀` ∈ [m], ∀j ∈ [n] (3)
and multiply its factors to get B ′C ′. Developing a 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.

heading: 2.5 UPCA with Dominant Permutations
text: We close this section with a special case of interest, where part of the data have undergone the same dominant 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 sizem×m. To make this precise, we define the multiplicity µ(Π) of a permutation Π ∈ Pm to be the number of times that Π appears as Π = Π∗j in (1) with j ranging in [n]. We have:
Theorem 3. Suppose that µ(Im) ≥ r+ 1 while µ(Π) < r for any other Π 6= Im. Then for a generic X∗ ∈Mr, we have that S∗ is the unique solution to the following consensus maximization problem
max dimS≤r #{x̃j | x̃j ∈ S ; j ∈ [n]}, (4)
where # denotes the cardinality of a set, and the maximization is taken over all subspaces S ⊂ Rm of dimension ≤ r.
Theorem 3 says that for sufficiently generic ground truth data X∗, the given data X̃ admit a natural partition into a set of inliers and outliers with respect to the linear subspace S∗:
X̃in := {x̃j | x̃j ∈ S∗}, X̃out := {x̃j | x̃j 6∈ 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.

heading: 3 Algorithms

heading: 3.1 Two-stage algorithmic pipeline for UPCA
text: We saw in the previous section that the UPCA problem (2) is well-defined (Theorem 1) and in principle solvable by a polynomial system of equations (Theorem 2). However, this polynomial system is at the moment intractable to solve even for moderate dimensions. On the other hand, Theorem 3 suggests the following algorithmic pipeline, for the case where there is a dominant
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, 33, 25, 45, 37, 48, 18] is employed to produce an estimate Ŝ of S∗ from X̃. At Stage-II of the pipeline, one feeds Ŝ and X̃ to an unlabeled sensing method [30, 32, 36, 23] which operates point by point, returning for every x̃j an estimate x̂j of x∗j . Here one may choose to threshold the x̃j’s based on their distance to Ŝ and apply unlabeled sensing on the outliers only. Alternatively, if extra computational power is available for dispensing with choosing a threshold, one may apply unlabeled sensing on every x̃j; it is this approach that we follow in the rest of the paper. This procedure is summarized in Algorithm 1.
Algorithm 1 Two-stage Algorithmic Pipeline for UPCA
1: Input: observed data matrix X̃, rank r 2: estimate Ŝ of S∗ ← outlier-robust PCA on X̃ . Stage-I 3: for j = 1, . . . , n do . Stage-II 4: estimate x̂j of x∗j ← unlabeled sensing on (x̃j, Ŝ) 5: end for 6: return X̂ = [x̂1, . . . , x̂n] estimate of X∗

heading: 3.2 A new method for unlabeled sensing: Least-Squares with Recursive Filtration (LSRF)
text: 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 the coordinate of the ambient space on which the residual error attains its maximal value, until r coordinates are left. The number of iterations is fixed as (m− r), so the overall complexity of Algorithm 2 is O(m2r2). We here also mention the time complexity of other unlabeled sensing methods for comparison: AIEM has complexity approximately O(m+ rr), PL has complexity at least O(kmr3) via second-order optimization, and `1-RR has complexity at least O(mr3 + k(m + r2)) 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 x̃j, basis B∗ of subspace S∗
2: v(0) ← x̃j, A(0) ← B∗ 3: for k = 1, . . . ,m− r do 4: c← A(k−1)†v(k−1) 5: i ′ ← argmaxi |v(k−1)i −A(k−1)i c| 6: remove the i ′-th entry of v(k−1) to get v(k) 7: remove the i ′-th row of A(k−1) to get A(k) 8: end for 9: return x̂j = A(m−r)A(m−r) † v(m−r) estimate for x∗j

heading: 4 Experimental Evaluation

heading: 4.1 Robust-PCA with permutation-induced outliers
text: 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]; see related work in section 1. We fix m = 50, n = 500. With dimS∗ = r = 1 : 1 : 49, we sample S∗ at random from the Grassmannian Gr(r,m). Then n points x∗j are sampled at random from the intersection of S∗ with the unit sphere of Rm to yield X∗. Let nin be the number of inliers X̃in and nout the number of outliers X̃out, with nin + nout = n. We consider outlier ratios nout/n = 0.1 : 0.1 : 0.9. With fixed nout/n, we set Π∗j to the identity for j ∈ [nin] and set Π∗j ’s for j > nin as follows. We consider both dense (α = 1) and sparse (α = 0.1) permutations. For a fixed α, we obtain Π∗j
by randomly choosing αm coordinates for each x∗j and applying a random permutation on those coordinates. As evaluation metric we use the largest among all r principal angles between Ŝ and S∗, denoted by θmax(S∗, Ŝ). Recall θmax(S∗, Ŝ) = 0 if and only if Ŝ = S∗.
Figure 1 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: i) 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 iii) 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.51sec for the computation of a single phase transition plot, Self-Expr is the slowest with 752sec, and DPCP and OP take 1.31sec and 5.62sec, respectively2.
Now let us look at what happens for permutation-induced outliers. For α = 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 as 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 is observed when the permutation ratio is decreased to α = 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; a justification for this is that both methods get initialized via the SVD of X̃, which yields a subspace closer to S∗ for smaller α. An interesting research direction is to analyze the theoretical guarantees of these methods for this specific type of outliers.

heading: 4.2 UPCA on synthetic data
text: Next, we evaluate the UPCA pipeline of Algorithm 1 on synthetic data. We keepm = 50 as before, and add spherical noise corresponding to a fixed SNR of 40dB. We get the estimate Ŝ of S∗ via DPCP [37] in Stage-I and apply the unlabeled sensing methods [36, 23, 30, 32] and Algorithm 2 in Stage-II to get X̂ from Ŝ and X̃. We distinguish between dense and sparse permutations.
2Experiments are run on an Intel(R) i7-8700K, 3.7 GHz, 16GB machine.
UPCA with dense permutations (α = 1). Figure 2 depicts the relative estimation error of X̂ for different outlier ratios from 75% (25 inliers) to 94% (6 inliers) and ranks r = 3, 4, 5. 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 AIEM(Ŝ)/CCV-Min(Ŝ) depends on the outlier ratio through the computation of Ŝ. Indeed, Ŝ is expected to be closer to S∗ for smaller outlier ratios, as we already know from Figure 1. In particular, for up to 75% outliers the estimation error of AIEM(Ŝ)/ 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 AIEM(Ŝ)/ CCV-Min(Ŝ) break down, indicating that the estimation of Ŝ failed. Finally, note that CCV-Min has at least half order of magnitude smaller estimation error than AIEM. This is due to our specific choice of the branch-&-bound 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 X̂ 0.42% away from X∗.
UPCA with sparse permutations (α ≤ 0.6). Figures 3b-3d show the relative estimation error of UPCA for α = 0.1 : 0.1 : 0.6, rank r = 1 : 1 : 25, and outlier ratio fixed to 90%, with Ŝ computed in Stage-I by DPCP [37] and X̂ computed via `1-RR [30], PL [32] or Algorithm 2 from X̃ and Ŝ in Stage-II. It is important to note that r = 25 = m/2 is the largest rank for which unique recovery of X∗ is theoretically possible [38, 39, 34, 35, 10, 24]. Figure 3a shows that θmax(S∗, Ŝ) always stays below 2◦, indicating the success of DPCP. Now `1-RR and Algorithm 2 have similar accuracy, but Algorithm 2 is more efficient than `1-RR, considering that computing X̂ takes 0.3sec for Algorithm 2 and 1.5min for `1-RR. Even though PL delivers X̂ in 1sec, it is not performing as well, which we attribute to its sensitivity on the particular basis of S∗ that is used to generate the data; this is not available here since DPCP returns the specific basis of dual principal components.

heading: 4.3 UPCA on face images
text: In this section we offer a flavor of how the ideas discussed so far apply in a high-dimensional example with real data. We use the well-known database Extended Yale B [14], which contains fixed-pose 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 a low-dimensional subspace. It turns out that for our purpose the value r = dimS∗ = 4 is good enough. Since each image has size 192× 168, the images of each individual can be approximately seen as n = 64 points x∗j , j ∈ [64] of a 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 (α = 0.4) permuting image patches of size 16 × 24 or 48 × 42, as shown in the second column of Figure 4. To generate a 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-permutation (outliers) are given without any inlier/outlier labels, and the task is to restore all corrupted images. This is a special case of visual permutation learning, recently considered using deep networks [26, 27].
The first column of Figure 4 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 1 for different unlabeled sensing methods and Ŝ computed by DPCP [37] (CCV-Min [23] is not included as branch-&-bound 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 if one takes into consideration that the methods are very efficient, requiring only 0.2sec (AIEM), 7sec (`1-RR), 0.2sec (PL) and 10sec (Algorithm 2), discounting the DPCP step, which costs 0.1sec, 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-&-bound and thus have in principle an exponential complexity in the number of permuted patches.

heading: 4.4 UPCA on data re-identification
text: Finally, we evaluate the UPCA Algorithm 1 for the task of data re-identification (see section 1) 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 Ŝ in Stage-I, and `1-RR [30], PL [32], or Algorithm 2 produces X̂ in Stage-II.
The first dataset consists of the test scores of m = 707 high-school students on 6 subjects during two different periods, together with the sum of the score tests for each period, thus n = 14. For 7 out of 14 tests, we apply random permutations of the student indices and thus have 50% outliers. With 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 α’s. Since `1-RR, PL, and Algorithm 2 are by design suitable for sparse
0.2 0.4 0.6 0.8 1.0
0.05
0.1
0.15
0.2
(a) high-school scores
0.2 0.4 0.6 0.8 1.0
0
0.1
0.2
0.3
0.4
(b) breast tumor features 0.20.40.60.81.0 0
0.1
0.2
0.3
0.4
permutations, their performance naturally degrades for large α. But up to α = 0.7 it aligns with our earlier findings in that Algorithm 2 tends to have superior performance on the average, and we also see that in that regime it also has the smallest variance.
The second dataset consists of all the benign cases in Breast Cancer Wisconsin (Diagnostic) [12]. It hasm = 357 patients and n = 30 features of a breast mass digitized image for each patient. We randomly permute the patient indices for 15 of the features thus having 50% outliers and set r = 4. Figure 5b shows the relative estimation error of X̂ for various permutation sparsity levels α, with the unlabeled sensing methods exhibiting the same trend as before. Remarkably, for α = 0.7, the UPCA Algorithm 1 incorporating Algorithm 2 in Stage-II reduces the original error of the data X̃ from 32.24% to 6.35% in 0.5sec, as opposed to 15.90% and 19.57% when `1-RR [30] or PL [32] are incorporated, respectively.

heading: 5 Discussion
text: Some interesting conclusions can be drawn from this work regarding privacy protection. First, it appears to be not secure for data providers to only partially permute the data, since, as we have seen, permuting only a 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 in 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 case where on 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 are 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.

heading: Acknowledgement
text: This work was funded by ShanghaiTech start-up grant 2017F0203-000-16.

Review summaries:
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.

- 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. - 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. - 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. - 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.  - 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. - Finally, the authors provide extensive experiments on their methodology on synthetic and real datasets. 

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.

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