Capturing the denoising effect of PCA via compression ratio

Authors: chandra sekhar mukherjee
nikhil  deorkar
jiapeng  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-05 20:16:03

Abstract: Principal component analysis (PCA) is one of the most fundamental tools in machine learning with broad use as a dimensionality reduction and denoising tool. In the later setting, while PCA is known to be effective at subspace recovery and is proven to aid clustering algorithms in some specific settings, its improvement of noisy data is still not well quantified in general. 

In this paper, we propose a novel metric called *compression ratio* to capture the effect of PCA on high-dimensional noisy data.
We show that, for data with *underlying community structure*, PCA significantly reduces the distance of data points belonging to the same community while reducing inter-community distance relatively mildly. We explain this phenomenon through both theoretical proofs and experiments on real-world data. 

Building on this new metric, we design a straightforward algorithm that could be used to detect outliers. Roughly speaking, we argue that  points that have a  *lower variance of compression ratio* do not share a *common signal* with others (hence could be considered outliers).

We provide theoretical justification for this simple outlier detection algorithm and use simulations to demonstrate that our method is competitive with popular outlier detection tools. Finally, we run experiments on real-world high-dimension noisy data (single-cell RNA-seq) to show that removing points from these datasets via our outlier detection method improves the accuracy of clustering algorithms. Our method is very competitive with popular outlier detection tools in this task.

Main paper: 
 introduction: 
 Principal component analysis, commonly known as PCA, is one of the most fundamental tools in machine learning. PCA is primarily used as a dimensionality reduction tool that transforms highdimensional data to lower dimensions for better visualization as well as a heuristic that reduces the complexity of the algorithms that are to be run on the data. On the other hand, it is also known to have certain denoising effects on high-dimensional data. This denoising phenomenon has been observed in different domains, including biological data [KAH19, VKS17] , speech data [Li18] , signal measurement data [ARS + 04, KHK19], image data [MBSP12] among others. The denoising effect of PCA has been extensively studied over the last decades [And58, HR03, Jac05, RVdBB96, Nad08, Nad14, VN17, MZ23, MZ24].One of the most fundamental problems in unsupervised learning is the analysis of data in the presence of community structures [CA16] . This includes clustering of such data [XT15] , visualization [TWT21] , outlier detection [AM13] , and others. The primary progress in understanding the denoising effect of PCA has been solely in clustering, particularly in connection to the K-Means algorithm [DH04, KK10, AS12] , where PCA in combination with a K-Means based iterative algorithm is shown to provide a good clustering of that dataset with mild assumptions with the underlying community structure. However, PCA seems to have a more "general" denoising effect in data, as it improves the performance of various downstream algorithms, including clustering [VKS17] as well community structure preserving graph embedding [HHAN + 21] and this denoising effect is evident in many real-world datasets.To this end, we propose a metric, called compression ratio, that quantifies PCA's improvement of high dimensional noisy data with underlying community structure in a geometric, and thus algorithm-independent manner2 .Compression ratio. Let u and v be two data points from a dataset and let Π t be the t-dimensional PCA projection operator. Then the compression ratio between the two points is defined as the ratio between their pre-PCA and post-PCA distance, which isu -v Π t (u) -Π t (v).In a dataset with a community structure, we show the compression ratio for intra-community pairs is higher than that of inter-community pairs even in settings where the pre-PCA inter-community and intra-community distances are very similar. We demonstrate (through a random vector mixture model) that this ratio gap reflects the denoising effect of PCA. As a consequence, PCA brings points from the same community much closer, improving the performance of downstream algorithms such as K-Means.As a motivating byproduct, we show that this metric can be used to design an outlier detection method that can detect points deviating from a community structure. Furthermore, we show that this method can improve the accuracy of clustering algorithms in real-world high-dimensional datasets.Outlier detection method. Our outlier detection is a simple process inspired by compression ratio. Intuitively, any data point that belongs to an underlying community should have large compression ratios with many points from the same community, whereas it will have a lower compression ratio w.r.t inter-community points. On the other hand, outliers will have more similar compression ratios with all the other points. This difference can be captured by the variance of the list of compression ratios between one point and all of the other points, with outliers having a lower variance of compression. Thus our algorithm simply removes points with low variance of compression.We analyze this simple algorithm in an extension of the standard random vector mixture model. We also compare our algorithm with popular algorithms such as the Local Outlier Factor (LOF) method [BKNS00] and KNN-dist [RRS00] as well as more recent methods such as Isolation forest [LTZ08] and ECOD [LZH + 22] through both simulations and experiments on real-world data. We show that this simple algorithm is very competitive with those popular outlier detection tools.Overall, we believe the effect of PCA on denoising becomes more significant if for each datapoint, there are many data points with large compression ratio variance.Real world experiments Finally, we test the relevance of compression ratio as a metric and the outlier detection method in real-world data. We focus on single-cell data, as it is both high dimensional (20, 000 -40, 000 dimension) and noisy [KAH19] , using datasets from a popular benchmark database [DRS20] with ground truth community labels. We first show that the average intra-community compression ratio is higher than the average inter-community compression ratio in all of the datasets. We then show that removing outliers in these datasets via our variance of compression technique improves the performance of clustering algorithms, such as PCA+K-Means, where we again outperform standard outlier detection methods.Organization of the paper In Section 2, we discuss our theoretical analysis. Concretely, we define the random vector mixture model and provide bounds on the intra-community and inter-community compression ratios. Next, we define our outlier detection metric and justify it in an extension of our generative model. Section 3 contains the simulation results validating the compression ratio metric and we also compare the performance of our outlier detection method with other methods.Finally in Section 4 we demonstrate that PCA exhibits an average version of compression ratio in real-world biological datasets [DRS20] and then test our outlier detection-based clustering accuracy improvement idea discussed above.PCA and its effect on noisy data has been subject to a lot of investigation in the last 50 years. Before 2008, most of the work focused on the asymptotic setting, where the number of points (n) and/or the dimension (d) are infinite (see [And58, RVdBB96, HR03, Jac05] and the references therein). In the last two decades, several works have also considered the finite sample setting [Nad08, Nad14] . These works have primarily focused on the denoising aspect of PCA in different variants of Gaussian noise. In a recent line of work [VN17] has studied the subspace recovery problem in the presence of bounded and (nice) sub-Gaussian noise. However, there seems to be no direct way to convert these results into a clustering setting. In comparison, we study PCA's denoising effect on data in random vector mixture model via the compression ratio metric, where the noise can be heavy sub-Gaussian.With regards to PCA's impact on data with community structure, the primary work has been in connection to K-Means. Here, one of the first works [DH04] showed that the outcome of PCA can be viewed as an approximation result to the K-Means outcome in clustering data. In this direction, a lot of progress has been made in the last two decades.A beautiful recent work [KK10] has shown that PCA followed by several iterations of K-Means along with modifications can cluster data with reasonable parameters in the random vector mixture model that we discuss here, which was then improved in [AS12] . Both of the works focused on the setting of n d (for example, [KK10] worked with n ≥ d 8 ). More recently, tighter results have been obtained in the context of the Gaussian-mixture model in [LZZ21] (still on the setting of n d 2 ).In comparison, we study PCA's relative compression in an algorithm-independent fashion, focusing on its effect on the geometry of the data in the high-dimensional setting of n = Ω(d) with sub-Gaussian noise. We are motivated to analyze this setting as single-cell datasets often have n < d.If i ∈ V j , 1 ≤ j ≤ k, x i = c j + e iwhere e i is sampled from D (j) . 2. outliers: If i ∈ V , then we sample p i,1 , . . . p i,k ∈ [0.5, 1]. Then u i = j α i,j c j + e i where α i,j = pi,j j pi,j and e i is sampled from D (k+1) .Let | V | = n o and n = n o + n c . To keep the results simple, we make the average variance of each distribution D (j) same, which is σ .The concept of Algorithm 1 is simple. If each cluster has a large number of points, then even if there are a large number of outliers generated from the random-mixture-outlier model, the outliers will have a lower variance of compression than all the clean points.First, let us obtain a lower bound on the variance of the compression ratio of clean points under the conditions of Theorem 2.8. We know that any clean point has high intra-community compression ratios. This implies that the expectation of the compression ratio for this point is high. On the other hand, the inter-compression ratio values are low. So just calculating the variance on the inter-community points yields a large value.For the sake of simplicity, we will define γ ≥ 2β √ σkd 1/4 . Then if we can show that under the other settings of Theorem 2.8, there is a separation in the variance of the compression ratios of the clean points and the outliers wheneverβ ≥ C σ √ log n σ, we prove the theorem.Lemma C.6. Let there be n c clean points in the random-mixture-outlier setting where min j |V j | = Ω(n/k) and γ ≥ 2β √ σkd 1/4 . Then the variance of all such points are lower bounded asC 4 • nc-|Vj | n • d 1/4 k • βσ σ -σ β•σ with probability 1 -O(1/n).Proof. Consider any point x i ∈ V j . Then the inter-compression ratio of x i with any intra-community point is lower bounded by0.25σ √ d σ √ k+α √ log n+2 √ σσ d 1/4 /(β) ≥ 0.25βσ σ d 1/4 with probability 1 -O(1/n).Then the average of the compression ratios for x i is lower bounded as0.25σ /σd 1/4 |Vj | n ≥ C3βσ /σd 1/4 kOn the other hand, probability 1 -O(1/n) we have that for any inter-community point, the compression ratio is upper-bounded with2σ √ d (γ-(2σ √ k-α √ log n-C2σ d 1/4 ) ≤ 2σ √ d βkσ d 1/4 /C2 ≤ 2C2σ/σ d 1/4 β•k .Then, the variance of compression of x i is lower bounded byEQUATIONNow, we aim to upper-bound the variance of compression for outliers. Here we want to show that since the underlying signal in any outlier is apart from the signal of any other point, they generally have a lower compression ratio with any other point, which then implies a lower variance of compression ratio.First, we show that as long as there are not too many outliers, their underlying centers (which are random mixtures of the community centers) will not be too close (which implies they will not have a high compression ratio).Let there be n o many outliers in the dataset generated via the random-mixture model where k ≥ log n. Let the set of outliers be V . Then, for with probability1 -O(n), min u,v∈ V u -v ≥ γ log n . Proof. Let | V | = n o .Then, for the underlying mixture-center any two points, denoted as u = j α 1,j c j and j α 2,j c j we say they are -far if min j |α 1,j -α 2,j | ≥ . Now, note that for any -far mixture-centers, we have uv ≥ 0.5 γ. Now, it is easy to see that the probability that there is a pair of mixed centers that is not -far is n 2 0 • ( ) k . Then, setting = 1/ log n and applying k ≥ log n gives that even for n 0 = n/2, there all pairs of mixture centers are 1/ log n-far with probability 1 -O(1/n).Then, we show that in such a case, the variance of compression for any outlier point is quite low even when measured crudely. Lemma C.8 (Variance of compression of outliers). Let there be a set of n o many outliers so that the underlying mixture-centers are pairwise 1/ log n-far Then under the condition of Lemma C.6, we have that the variance of compression for any outlier is upper bounded by4C2 log n(σ/σ )d 1/4 β•k 2 with probability 1 -O(1/n).Proof. Consider any outlier u i ∈ V 0 . First, consider the compression ratio between u i and any v that is clean. Where u i = j α j c j + e i and v = c j + e i .Next, remember that as every α j ≥ 1/2k, we have max j α j ≤ 0.5.Then, from the definition of γ-spatially unique centers we havej α j c j -c j ≥ j =j α j c j -(1 -α j )c j ≥ 0.5 j =j α j c j -c j ≥ 0.5γThen, following the analysis of Lemma C.6, we can show that in all such cases, the compression ratio is upper bounded by 4C2σ/σ d 1/4 β•k .On the other hand, consider any two outliers. Then their compression ratios are upper bounded by4C2 log nσ/σ d 1/4 β•k(essentially replacing γ by γ/ log n in the center-distance calculation).Then, we can upper bound the variance of compression for an outlier as1 n | V |( 4C 2 log nσ/σ d 1/4 β • k ) 2 + (n -| V |)( 4C 2 σ/σ d 1/4 β • k ) 2 ≤ 4C 2 log n(σ/σ )d 1/4 β • k 2 [applying k ≥ log n ]Proof of Theorem 2.8 Lemma C.6 shows that in the setting of Theorem 2.8, the variance of compression ratios for a clean point is lower bounded byC 4 • n-|Vj | n • d 1/4 k • βσ σ -σ βσ 2 .Next, Lemma C.8 shows that the variance of compression ratios for an outlier is upper-boundedas 4C2 log n(σ/σ )d 1/4 β•k 2Both the aforementioned happen for all outlier and clean points withprobability 1 -O(1/n).Then, to show that with high probability, the variance of compression ratios of any clean point is higher than the variance of compression ratios of any outlier isC 4 • n -|V j | n • d 1/4 k • βσ σ - σ βσ 2 > 4C 2 log n(σ/σ )d 1/4 β • k 2 =⇒ √ d k 2 • n -| V | n • βσ σ - C 5 log nσ σ β > 0 [For some constant C 5 ] =⇒ √ d k 2 • 0.5βσ σ - C 5 log nσ σ β > 0 [As n -| V | ≥ 0.5n]Then, as long as β ≥ 10C 5 σ/σ √ log n, this equation is satisfied.Here we show some results in the case of k = k -1 + c. The main challenge in theoretically proving our bounds for k = k -1 comes from Theorem B.8. A key ingredient towards proving Theorem B.1 is the following spectral gap.(P k Z ) T -(P k Z ) T W ≤ 2 E Z δ k (Y )In general we work with the natural assumption δ k-1 (Y ) >> E Z . However, in our model we have s k (Y ) = O( E Z ). This follows from Weyl's inequality, which states that if Z = Z + E Z and (k )-th singular value of B is 0, then (k -1 + c)-th singular value of Z is upper bounded by O( E Z ) for any c > 0.Thus δ k (Y ) = O( E Z ) for any k ≥ k, and our previous results alone cannot prove relative compressibility.Here we bypass this issue to a loose but non-trivial extent. First we note that the inter-community compression can only decrease if the the projection dimension increases. Thus we have that for anyk ≥ k, ∆ X,k (i, i ) ≤ ∆ X,k-1 (i, i ).Theorem D.1. Let us consider the random vector model as in Theorem B.1. Let Let k = k -1 + c and any 0 < f < 1. Then we have that with probability 1 -O(1/n),1. If (i, i ) is an inter-community pair, then ∆ k ,X (i, i ) ≤ ∆ k-1,X (i, i ) 2. If (i, i) is an intra-community pair, then∆ k-1,Y (i, i ) ≥ c j -c j 2 + d(σ 2 j + σ 2 j ) + 12 √ d log n P k-1 Y (y i -y i ) 2 + 4C 2 0 σ 2 (d + n)c 2 f 2 for all but c 2 /f 4 pairs of points with probability 1 -O(1/n).Proof. The inter-community bound follows from definition and the numerator of the intra-community bound follows from Lemma B.2. We now prove the denominator (post PCA distance bounds) for the intra-community case.Let us denote with P k1,k2 Y the projection operator due to the k 1 -th to k 2 -th top singular vectors of Y .Then for any vector u we haveΠ k X (u) = Π k-1 X (u) 2 + P k,k Y (u) 2 .Then we are left with bounding P k,k Y (u) 2 where u = y i -y i so that i ∈ V j , i ∈ V j . We aim to show that if k -k is small then this value is small as well.We first represent Y with its SVD decomposition. l and r represent the -th left singular vector and right singular vector of Y respectively. Then we have Y = t =1 s i (Y )l (r ) T where t = rank(Y ). Then the projection of y i due to the -th principal component of X is l , y i = s (Y )r , i where r ,i is the i-th entry of the -th right singular vector. Then we have≤ s k (Y ) k =k (r ,i ) 2Here recall that each r is a n-dimensional vector with unit norm, i.e. r = 1. Then for any f < 1, the number of coordinates of r that are larger than f is less than 1/f 2 . Thus considering all the k ≤ ≤ k -1 + c, the total number of entries that are larger than f is less than c/f 2 . Then, for all but c/f 2 many points y i we haveP k,k-1 Y (y i ) ≤ s k (Y ) • f • c. Here we substitute s k (Y ) ≤ E Y ≤ C 0 σ √ d + n with probability 1 -O(n -3 ).This implies that with probability1 -O(1/n) P k,k-1 Y (y i -y i ) ≤ 2C 0 σ √ d + ncffor all but c 2 /f 4 pairs of points. This concludes our proof.It should be noted that this is a much looser bound as compared to our (k -1)-PC compression metric, especially in the paradigm where noise dominates the ground truth distances. As we discussed, the main reason that Theorem B.1 does not directly work for k > k -1 can be pinned down to the following technical challenge. ) realizes its spectral norm, which is unlikely to be the case for most noise e vectors, due to the inherent randomness in them. A better analysis of this term will allow us to extend the result of Theorem B.1 beyond k = k -1, which is what we observe in reality. For real datasets, the compression factor does not change much if the PCA dimension is changed by a small value. Furthermore, a tighter understanding of (P k-1 Z -P k-1 Z )e will also enable to us make progress towards proving optimality of perhaps the simplest spectral clustering algorithm for the SBM problem, as conjectured by [Vu18] . There has indeed been some progress very recently [MZ24, MZ23] in some very specific settings, i.e. SBM (stochastic block model). Generalizing these results to the random vector mixture model is an outstanding open question. In Section 4 we showed the average of community-wise average of intra and inter-community compression ratios for the datasets in [DRS20] for PCA dimension=k -1. Here we present the results for each community of the datasets. We observe that even in the community-level metric, the intra-community compression ratio is higher than the inter-community compression ratio for all datasets.E.3 NMI and purity index improvement for PCA-dim=k -1Now, we continue with providing more experimental results. First, we note down the NMI improvement when 5% and 10% of the points are removed in the setting of PCA dimension= k -1.Next, we add the initial purity scores when running PCA( dimension=k -1)+K-means on the datasets in Table 6 .Then the improvement in purity index due to 5% and 10% points removal are recorded in Figures 5 and 6 . For brevity, we show the improvement in NMI and purity index for 10% point removal in Figures 7 and 8 respectively. As one can observe, our method continues to be the most consistent, being the best method in most datasets. Indeed, in this case our performance is even comparatively better than in the case of PCA-dimension=k -1.In this paper, we have quantified PCA's denoising effect in high dimensional noisy data with underlying community structure via the metric of compression ratio. As an application, we have designed an outlier detection method that improves the community structure of datasets. We note two interesting theoretical and algorithmic questions. i) Providing a more tight bound on the compression ratio seems an exciting and hard direction. ii) Using compression ratio as a metric for clustering algorithms also seems an interesting direction, especially for single-cell-RNA-seq datasets.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The data is publicly available and we include its source. The supplementary material includes our simulation code, algorithms, and experiments. Guidelines:• The answer NA means that paper does not include experiments requiring code. • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
random vector model and relative compression of pca: 
 To theoretically study the relative compression of PCA, we use a high-dimensional mixture model, similar to one in [KK10, AS12] . We call this a random vector mixture model. This can also be interpreted as a signal-plus-noise model where the signal imposes a community structure on the data. The dataset of interest is a set of n many d dimensional real vectorsx i ∈ R d , 1 ≤ i ≤ n,which is together represented as the dataset X. We express X as a d × n matrix, with each column representing a data point. The data points have an underlying hidden community structure that is expressed as a partition of [n] := {1, . . . , n} into k many sets V 1 , . . . , V k such that each i ∈ [n] lies in any one V j . We then have the following problem structure.1. Each cluster V j , 1 ≤ j ≤ k is associated with a ground truth center c j ∈ R d .2. Additionally, each cluster V j is associated with a distribution D (j) such that D (j) is a coordinate wise independent zero mean distribution. For ease of exposition, we define the support of D (j) to be [-α, α] d for some α (which can also depend on n, d), but our methods also directly apply to sub-Gaussian distributions where each coordinate has a constant sub-Gaussian norm (resulting in O( √ d) norm of any column vector). Then α would be replaced with C log n for some constant C in our bounds.Then, the dataset X is set up as follows. Definition 2.1 (Random vector mixture model). For each i ∈ [n], if i ∈ V j , then x i = c j + e i where e i ∼ D (j) , i.e. e i is independently sampled from D (j) . Here we abuse notation and denote both i ∈ V j as well as x i ∈ V j .With this setup, now we define the PCA projection operator and the compression ratio metric formally.Definition 2.2 (The PCA operator Π k X ). Let X be a d × n matrix. Then the k dimensional PCA projection operator is simply the projection operator onto the first k principal components of X.Next we formally define the compression ratio metric. Definition 2.3. For any pair (i, i ) we define the k -PC compression of the pair of vectors in X as∆ X,k (i, i ) = x i -x i Π k X (x i ) -Π k X (x i )Before describing our results, we define certain parameters of the model.1. The maximum variance of the entries, σ is defined asσ 2 = max 1≤j≤j,1≤ ≤d Var[D (j) ]2. The average variance of a column in a distribution D (j) , noted as σ j is defined asσ 2 j = 1 d V ar([D (j) ]).Here, σ j √ d is the perturbation on the data points of V j due to the noise.In this direction, we first lower, and upper bound the (k-1)-PC intra-community and inter-community compression ratios respectively, as a function of the maximum variance, average variances, spectral structure of the noise and signal, and distance between the centers of the model, which can be found in Theorem B.1.Although our result applies to any set of centers, the spectral properties of the resultant matrix, and their interactions make the result hard to interpret. To give more insight into our bounds, we instead define a restricted (still natural) structure on the centers, which allows us to give a more interpretable result in this case. For simplicity, we also work in the setting where d ≥ 10α √ n log n. Definition 2.4 (Spatially unique centers). We say a set of vectors C = {c 1 , . . . , c k } are γ-spatially unique, if we have that min1≤j≤k min v∈Span(C\c j ) c j -v ≥ γThis implies that each center has a unique pattern that cannot be approximated by a combination of the other centers. Here note that γ ≥ min j =j c j -c j . For example, such a property is expected if the centers are mutually orthogonal. One can also think of them as vertices in a high-dimensional regular polygon. Then, we give some sufficient conditions for the separation of intra-community and inter-community compression ratios of PCA.Theorem 2.5 (Separation of compression ratio). Let γ ≥ C max{σ √ kd 1/4 , σ √ k + α log n} for some constant C. Furthermore, let i ∼ i denote that y i and y i belong to the same underlying community. Then, the following holds.1. The perturbation of the points due to noise can be much larger than the distance between the community centers, i.e., the noise dominates the distance between the centers.1 -O(1/n), min (i,i ):i∼i ∆ X,k-1 (i, i ) ≥ 4 • max (i,i ):i i ∆ X,k-1 (i, i )This shows that the compression ratio of PCA provides a separation between intra-community and inter-community pairs even in a setting where the noise highly dominates the distance between the centers. One can find a more general theorem w.r.t spatially unique centers in Theorem C.4.A natural question is whether post-PCA distance is a good metric for denoising due to PCA. In this regard, we point out that the compression ratio has an added normalization property. For example, consider the case where all pair-wise center distances are the same. In such a case, the post-PCA distances are dependent on σ j , so communities with larger variances have larger intracommunity distances. However, this gets normalized in the compression factor as per Equation (9) of Theorem C.4, as the numerator also has a dependency on σ j .Input: data X, PCA dimension k , number of outliers o.for i = 1 to n do SC[i] ← VAR∆ X,k (x i ) {VAR∆ X,k defined in Eq. 1} end for return o many indexes with lowest SC values.Now, we discuss the usefulness of compression ratio on outlier detection. We first describe the notion of variance of compression ratio. Definition 2.6 (Variance of compression ratio). Given a dataset X and a PCA dimension k , variance of compression ratio of a point u ∈ X is defined asEQUATIONwhere ∆ X,k (i, i ) =x i -x i Π k X (x i )-Π k X (x i )is the compression ratio between points i and i . That is, it is simply the variance of the list of compression ratios of x i with all the other points x i .Then, our intuition is that if data consists of many points from the high dimensional mixture model, as well as several outlier points that don't share a common signal (center), they have a lower variance of compression ratio. We concretize this notion with the following simple detection algorithm 1.Mixture-model with outliers Now let us consider an extension of the mixture model in Definition 2.1 to incorporate outliers. Definition 2.7 (Mixture model with outliers). Let X be a d × n dataset with the partition V 1 , . . . , V k , V , a set of k centers {c j } k j=1 and distributions {D (j) } k j=1 + 1 with the following generation method.1. clean points: If i ∈ V j , 1 ≤ j ≤ k, x i = c j + e i where e i is sampled from D (j) . 2. outliers: If i ∈ V , then we sample p i,1 , . . . p i,k ∈ [0.5, 1]. Then u i = j α i,j c j + e i where α i,j = pi,j j pi,j and e i is sampled from D (k+1) .Let | V | = n o and n = n o + n c . To keep the results simple, we make the average variance of each distribution D (j) same, which is σ .Such a scenario can occur in many different settings. For example, consider single-cell datasets which is a popular biological data type. Here each data point is a cell and the features (which are high, such as 20, 000) are specific gene expressions, A primary task here is to obtain cell sub-populations . c j -c j = O(σ √ d) (the noise is significant) 2. γ ≥ 2C σ 3/2 /σ • k • d 1/4 log nThen, for any n 0 ≤ n/2, the first n 0 points ranked by Algorithm 1 all belong to the outlier group ( V ) with probability 1 -o(1).We discuss the connection between our results and the role of spatially unique centers in Appendix C. The proof of Theorems 2.5 and 2.8 can be found in Appendix C and C.2 respectively. This gives us initial theoretical evidence that in the random-mixture model with outliers, our simple outlier detection method can detect outliers when a non-negligible fraction of the points are outliers. Next, we use simulations of our model to test the efficacy of our outlier detection method and its impact on the community structure of data and compare them with some popular outlier detection methods. 
simulations for outlier detection: 
 In this section, we first describe different instantiations of the random-vector mixture model, observe the intra-community and inter-community compression ratios in them, and then run simulations in the outlier mode. All simulations and experiments were run on a 2020 M1 MacBook Pro with 16 GB of memory within 1.5 hours of total running time.Simulation setup For this setup, we set n = 3000, d = 1000, and k = 3, with each community having the same number of points. For simplicity, we choose 3 equidistant centers, with c i -c j = c. We set the noise distributions to be Bernoulli distributions with variance σ 1 , σ 2 , σ 3 respectively. We work in two primary settings, of equal and unequal noise.i) Equal noise. Here we have σ j = σ for all i. ii)Unequal noise. Here one of the communities has variance 2σ, whereas all the other communities have variance σ.Then, we test the algorithms for three values of σ in the following manner.• Low noise: We choose σ : c j -c j ≈ 3σ √ d. This implies distance between the centers dominates the perturbation due to noise. • Significant noise: Here σ :c j -c j ≈ σ √ d.Here the noise norm and distance between centers are of the same order. • High noise: We have σ : c j -c j ≈ 0.3σ√ d.Here the noise heavily dominates the center distances.Let us look at the equal noise setting, i.e. the case where the variance of noise distributions for all communities are the same. We observe that in the low-noise setting, all intra-community compression ratios are higher than all inter-community compression ratios. As the noise increases, the gap between them decreases, so that in the high-noise setting, there is now an overlap between intra-community and inter-community compression ratios. We demonstrate this in Figure 1a . This further indicates that compression ratio is indeed a useful metric even when the noise has a strong perturbation effect on the data (even though there will be no clean separation between intra-community and inter-community compression ratios once the noise is very high). Now, we discuss the outlier detection, starting with the simulation setup in this case. We follow the random-mixture-outlier model and add outlier points along with the clean points as follows.We add n o = n c /10 outliers following definition 2.7. That is, we randomly choose α 1 , . . . , α 3 and then a random mixture-center is chosen as j α j c j , and then we add a random noise vector from the Bernoulli distribution of variance σ 4 .Outlier detection algorithms for comparisons Outlier detection has been an active area of study in unsupervised learning, providing several influential algorithms. In a recent, comprehensive benchmarking of outlier detection algorithms, [HHH + 22] compared the performance of several unsupervised learning algorithms on different datasets. They found that for unsupervised outlier detection methods, success was related to whether the underlying model of the data assumed by the outlier detection method followed the dataset at hand. They found that for local outliers, the popular Local Outlier Factor (LOF) method [BKNS00] performed the best statistically, whereas for global outliers, KNN-dist (where the outlier score is simply the distance to the K-th nearest neighbors) [RRS00] performed the best. Owing to their generally impressive performance, we use them for comparison with our variance of compression method. Furthermore, we select a popular method called Isolation forest [LTZ08] and also a very recent and popular outlier detection method ECOD [LZH + 22]. We also use PCA+method for each of the methods as benchmarks, as both outliers and clean points are perturbed by zero-mean noise, and we now understand PCA can help mitigate the effect of said noise, as discussed in Section 2.We compare the AUROC values of the 5 outlier methods of interest in these settings. We record the results in Figure 2a and 2b for the equal and unequal noise settings respectively. As we can see, our method results in the highest AUROC value, followed by PCA+KNN-dist. we make two observations. i) The performance gap between variance-of-compression and the next best method is higher in the unequal noise setting.ii)As the noise level increases, the gap between our method and PCA+K-NN dist increases.These two points further highlight the compression ratio's normalizing effect as well as effectiveness in high noise settings.Here we remark that in real-world data, while some points may indeed behave like outliers, they need not all be the same kind of outlier. Thus, we would like to verify our method's performance in the presence of a different kind of outlier, which we concretize below.We consider the case that some points may have significantly higher noise perturbations than others. In this setting, we randomly select some points, and we generate some points with c • σ coordinate-wise variance, where c = 8 for our experiments (recall that the noise in the other points has a coordinate-wise σ variance). It is well known that if noise is low-dimensional, then such outliers are well captured by LOF. We observe that while in the low noise setting our performance is worse than the other methods, as the overall noise increases, the performance of our method is more comparable to the other methods. We record the results in Figure 1b . This shows that our outlier detection method is adept at detecting different kinds of outliers, outperforming popular outlier detection tools in some settings, and being competitive to them in others. We also observe that as the overall noise in the dataset increases, the performance of our method compared to the other outlier detection tools improves. This further highlights the power of compression ratio when especially dealing with noisy data. Having demonstrated the validity of our outlier detection method in two different settings, across different noise levels, we now focus on real-world datasets. 
real world experiments 4.1 datasets of interest: 
 In this section, we provide experimental results to exhibit the validity of compression ratio as a metric and the usefulness of our outlier detection method in improving the community structure of datasets.We focus on single-cell RNA sequencing datasets. The dataset consists of n many data points, each corresponding to a cell. The features are gene expressions, and for the cell, the expression of some d ≥ 10, 000 genes are recorded. A fundamental problem here is to identify sub-populations of interest. However, the problem is challenging as the biological process of recording gene expressions is error-prone [THL + 19], and gene expressions within the same population may also vary due to internal randomness. Furthermore, experiments can cause cells to get merged during gene-expression recording [XL21] . This makes single-cell RNA sequencing data a good testing ground for high dimensional noisy data with outliers and underlying community structure.In this direction, we consider the single-cell RNA sequencing datasets from a benchmark paper [DRS20] . These datasets also have moderate to highly reliable ground truth labels, that help us understand the usefulness of our metrics and our algorithm. These datasets vary in the number of cells, genes, clusters, cells per cluster, and the "difficulty" of clustering. A summary of the datasets is provided in Table 4 in Appendix E.1.As discussed in Section 2 and described in Theorem 2.5, our primary result showed that the intra-community compression ratios are higher than inter-community compression ratios in a large range of parameters. Here we look at average statistics of compression ratio to provide a first layer of evidence supporting this phenomenon in real-world data. We define the following metric. For any community V j , we define the average intra-community compression ratio asintra X,k (V j ) = E i,i ∈Vj x i -x i Π k X (x i -x i ) ] Similarly, the average inter-community compression ratio is defined as inter X,k (V j ) = E i∈Vj ,i ∈[n]\Vj x i -x i Π k X (x i -x i ). This gives an average measurement of the compression ratio in the dataset. In this regard, we find that for each of the 9 datasets and each of the communities in the dataset, the intra-community compression ratio is higher than the inter-community compression ratio. We provide the results in the Appendix E.2. Here, for brevity we present the average of intra X,k-1 (V j ) and inter X,k-1 (V j ) for each dataset in Table 1 .Next, we study the usefulness of our outlier detection method in these datasets. Unlike our simulations, there is no ground-truth labeling for outliers. Rather, we assume that in each community (as defined by the labels provided with the dataset), some points may behave more like an outlier, in that they may be a mixture of different signals. These can also be points that have uncharacteristically high noise compared to the rest of the data points. In such a case, these data points may muddle the community structure in the datasets, and thus, removing them may improve the community structure of the datasets. We capture this improvement by observing the change in the accuracy of clustering algorithms when some outlier-like points are removed from the dataset. For our experiments, we choose PCA+K-Means as our clustering algorithm, as it is known to be effective in single-cell datasets [VKS17, KAH19] .Experimental setup For each of the datasets, we do the following. Let k be the number of communities. We apply some c-dimensional PCA and then run a standard implementation of K-Means with k-centers on the post-PCA data and record the NMI and purity score, which are popular clustering accuracy metrics. This gives us a starting point. Then, for each dataset, we apply 9 outlier detection methods. The algorithms are our variance-of-compression-ratio method, and the original and PCA-added versions of LOF, KNN-dist, Isolation forest, and ECOD. We have two settings.First, we set c = k -1 (following our theory), and obtain the initial PCA+K-means results in Table 2 . Then, we remove 5% of the points according to the outlier score and then run PCA+K-Means on the rest of the dataset and obtain the new NMI values. Next, we repeat the same experiments by removing 10% of the points. Additionally, we also use c = 2k, and there, calculate the outcome only for 10% points removal, primarily to reduce redundancy. This is to test the sensitivity of the methods to the choice of PCA dimension.As a comprehensive summary, we calculate the performance rank of the methods on all the datasets in each of the settings. We record the results in Table 3 . As can be observed, we obtained the best rank in 5 out of 6 settings. The performance of each method for each dataset in the settings can be found in Appendix E. Robustness to choice of dimension Finally, we note that the compression ratio is not overly sensitive to the choice of PCA dimension, and if we use more dimensions than the number of communities, we still get favorable results. For theoretical support, we show in Section E.4 of the appendix that the compression ratios of most points change only mildly when k > k. In terms of experiments, we verify it as follows. For k = 2k, we calculate the average intra-community and inter-community compression ratios in Appendix E.4 and find them to be consistent with Table 1 . As in the case with PCA dimension=k -1, our methods have the best performance in terms of improving clustering performance.Limitations Finally, we note a few limitations with our outlier removal algorithm. First, the algorithm is dependent on selecting a reasonable removal percentage. While we observed greater NMI improvement with greater removal rates, it is important to understand what is a suitable choice for different datasets. Another concern is that our outlier detection tool may not be optimal for handling highly unbalanced communities, as a very small community will show a lower variance of compression ratio. These remain interesting research directions. We note more future directions in the Appendix F.In Sectiion B we obtain our first, generic proofs for compression ratio. Next, in Section C we interpret our results through the lens of spatially unique centers, and also prove our variance of compression result on outlier detection in this setting. Next in Section D we extend the results of Section B when number of components is more than k + 1.Section E contains continuation of experimental results from the main paper. We conclude with some future directions in Section F.In this section, we describe our primary compression ratio related result in the random vector mixture model. We first describe our result when the projection dimension is k -1. We first define some notations and useful results that we will use.We first define the SVD projection operator for a matrix X. Let the k -dimensional SVD projection operator for a matrix X be P k X . Next, for the dataset matrix X, we denote by Y its centered version. Then we haveΠ k X = P k Y .Then the compression ratio of the data pair (i, i ), defined asx i -x i Π k (x i -x i ) is in fact y i -y i P k Y (y i -y i ) .Then we have the following bound on the compression ratios in the random vector mixture model. Theorem B.1 (Main result). Let X be a d × n dataset setup in the random vector mixture model with k underlying communities, so that all centers c j and all column vectorsx i ∈ X are in [-α, α] d .Let Y be the corresponding centered dataset. Considering the following notations, 1. δ k (M ) := s k (M ) -s k +1 (M ) for any M , 2. σ 2 be the maximum variance of the random variables,3. N := C 0 σ √ d + n for some constant C 0 If σ 2 ≥ C 1 log nn for some constant C 1 then with probability 1 -O(1/n) we have that the (k -1)-PC compression ratio, ∆ X,k-1 (i, i ) of all intra-cluster pairs (i, i ) is lower bounded asEQUATIONSimilarly, the compression ratio of all inter-cluster pairs (i,i') is upper bounded by∆ X,k-1 (i, i ) ≤ d(σ 2 j + σ 2 j ) + c j -c j 2 + 12α √ d log n √ 2 c j -c j -2 σ √ k + C 1 • α • √ log n + 2N • cj -c j 2 +2dσ 2 +12 √ d log n δ k-1 (Y )(3)with probability 1 -O(1/n).Here we make the following remark about the range of the datapoints.We start with the definition of the norm operator • , which we use in the following two contexts.1. If u is a d dimensional vector, then u denotes the 2 norm of u, which isd i=1 (u i ) 2 . Then u -v is the 2 distance between the two vectors. 2. If M is a d × n matrix M , M denotes the spectral norm of the matrix. That is, M = max u, u ≤1 { M u }We follow this by defining some more structures related to random matrices.1. For any matrix M , we denote M := E[M ]. Then by definition, X is a d × n matrix such that if i ∈ V j , the i-th column of X is c j (as D (j) is a coordinate wise zero mean distribution), the ground truth center of V j . Thus, we denote by X as the ground-truth or expectation matrix of X. Similarly Ȳ is the center matrix of Y (recall that Y is the column centered matrix of X). Furthermore let Mi be the i-th column of M . Then ȳi -ȳi = xi -xi for any (i, i ) pair. Thus we can call Ȳ as the ground truth matrix of Y . 2. Corresponding to any matrix M , we denoteE M := M -E[M ].3. Choice of subscripts: From hereon we use the subscript i to denote the columns of X and Y . We use the subscript j for cluster identities and for rows of the matrices or the column vectors.With this a background, we give a short sketch of the proof.Looking at the numerator and denominator separately: Proving the relative compressibility result requires the following results in turn. Recall that the compression ratio is the ratio between pre PCA and post PCA distances between pair of datapoints and we want to lower bound "intracommunity" compression ratio and upper bound "inter-community" compression ratio. This means we need the following bounds to prove Theorem B.1.1. For the intra-community pairs of vectors, prove a lower bound on the pre PCA distance and upper bound on the post PCA distances. 2. For the inter-community pairs of vectors, prove an upper bound on the pre PCA distance and a lower bound on the post PCA distance.We first obtain the pre PCA distance bounds, which are straightforward to obtain using the fact that the randomness in the vectors of X are coordinate wise independent, and that y i -y i = x i -x i for any (i, i ) pair.Lemma B.2. Let y i and y i be two vectors (datapoints) of Y with ground truth communities V j and V j respectively. If j = j then we have y i -y i ≥ 2dσ 2 j -12α √ d log n with probability 1 -O(n -3 ), otherwise if j = j then we have y i -y i ≤ d(σ 2 j + σ 2 j ) + c j -c j 2 + 12α √ d log n with probability 1 -O(n -3 ).Proof. We know that for any (i, i ) pair y i -y i = x i -x i . Using this fact we prove the bounds on the datapoints of X.First we consider the case when x i and x i belong to the same community. Thenx i -x i 2 = d =1 ((x i ) -(x i ) ) 2 .Here for each we define w = (x i ) -(x i ) = (c j ) + (e i ) -(c j ) - (e i ) = (e i ) -(e i ) . Then E w 2 = E[((e i ) ) 2 ] + E[((e i ) ) 2 ] = V ar((e i ) ) + V ar((e i ) ).We define σ 2 l,i = V ar ((e i ) ) (to use the more familiar row major representation). Recall that both e i and e i are sampled from D (j) and σ 2 j is the average of variance of the coordinates of the distribution D (j) . i.e., E w 2 = d =1 σ 2 l,i + σ 2 l,i = 2dσ 2 j . Now recall that the random variable w is in the range [-2, 2] for any . Then applying Hoeffding bound on this setup we getPr d =1 w 2 ≤ 2dσ 2 j -12α √ d log n ≤ n -3 .Thus, if x i and x i belong to the same community then with probability 1 -O(n -3 ) we havex i -x i ≥ 2dσ 2 j -12α 2 √ d log n.Similarly, if x i and x i belong to different communities V j and V j , we have the random variable w = (x i ) -(x i ) with mean (c j ) -(c j ) (due to the difference in the centers ) and variance σ 2 l,i + σ 2 l,j , where we define c ,j = (c j ) . Then E w 2 = σ 2 l,i + σ 2 l,j + (c ,j -c ,j ) 2 andE d =1 w 2 = d =1 σ 2 ,i + σ 2 ,j + (c ,j -c ,j ) 2 = d(σ 2 j + σ 2 j ) + c j -c j 2Applying Hoeffding bound we getPr d =1 w 2 ≥ d(σ 2 j + σ 2 j ) + c j -c j 2 + 12α √ d log n ≤ n -3 .Thus if x i and x i belong to different communities then with probability 1 -n -3 we have x i -x i ≤ d(σ 2 j + σ 2 j ) + c j -c j 2 + 12α √ d log n.Now, we move into the analysis of post-PCA distances, which is the more technical part of the proof.High-level idea. The idea behind the proof is simple.In our setup, X = E[X] is the ground truth matrix, such that if the i-th column of X belongs to V j , then the i-th column of X is c j . Thus, X is rank k and thus P k X (c j -c j ) = c j -c j . This implies Ȳ has rank k -1 and P k-1 Ȳ (c j -c j ) = c j -c j . The crux of the proof is to show that P k-1 Ȳ can be well approximated with P k-1 Y , even when Y and Ȳ differ significantly (due to the noise).To achieve this result we use tools from spectral analysis of random matrices, i.e. tools that study the behavior of eigenvalue and eigenvectors of random matrices. Here we face two hurdles.1. First we note that the matrix Y is rectangular and unsymmetric. The vast majority of tools in spectral analysis of random matrix theory are focused on symmetric matrices.To use this to our advantage we focus on a closely related symmetric matrix through the following symmetrization trick, which is essential to the proof. We define the matrix Z asZ := 0 Y Y T 0. This is a d + n × d + n symmetric matrix. We show that P k-1 Y can be analyzed through P k-1 Z and then approximate the second projection operator using P k-1 E[Z] , borrowing tools from classical random matrix theory. This gives us preliminary post PCA distance bounds expressed using Y -Ȳ . 2. Then obtaining the exact bounds of Theorem B.1 require bounds on the spectral norm of Y -Ȳ . There exists a rich literature on spectral norm of random symmetric matrices with independent entries, but Y -Ȳ does not satisfy this either. This is because, since Y is obtained by subtracting the column mean from each vector of X, the entries of Y , and thus Y -Ȳ are not independent either. To this end, we first obtain the said properties for X -E[X] borrowing tools from [Vu18] on our symmetrization trick, and then accommodate for the effect of centering using results from [Han14] to complete our proof.We now describe the symmetrization trick and its implications in detail.We start by recalling the symmetric matrix corresponding to Y , Z = 0 Y Y T 0 . As per our notations we denote Z = E[Z] and then we haveZ = 0 Ȳ Ȳ T 0 . Furthermore we have E Z = Z -Z.Then the eigenvectors of Z and singular vectors of Y (and similarly Z and Ȳ ) are related as follows.Fact Here we also formally define P k M for symmetric matrices M as in this case we work with eigenvectors corresponding to top eigenvalues, instead of top singular values (as in case of Y ), for clarity.Remark B.4. For any matrix M , we have defined P k X as the matrix whose rows are the top k singular vectors of M .However, when we discuss a symmetric matrix M , P k M is a matrix whose rows are the eigenvectors corresponding to the top k eigenvalues of M . This in turn gives us the following results connecting P k Y and P k Z .Fact B.5. Let 0 n be the n dimensional zero vector. Furthermore let v|0 n := v 0 n for any vector v.Then for any d-dimensional vector v we haveP k Y v = √ 2 P k Z (v|0 n )This result allows us to work with the symmetric matrices Z and Z instead of Y . Now we obtain the results needed to approximate P k Z with P k Z .Difference in spectral projections of Z and Z: Here we use the Davis-Kahan Theorem [DK70] along with a result by Cape et. al. [CTP19] to obtain an upper bound between the norm of difference of the leading eigenspaces of Z and Z under some appropriate orthonormal rotation that we shall use to obtain our results. The main reason behind using these tools is that the SVD projection matrix due to Z is well behaved. ). Let U and Û be two p × k matrices such that the columns of U (and similarly Û ) comprise of k many unit vectors that are mutually orthogonal.Then there exists a k × k orthonormal matrix W U such thatsin Θ U, Û ≤ U -Û W U ≤ √ 2 sin Θ U, ÛCombining them we get the following result.Theorem B.8. Given the matrices Y and Ȳ and Z and Z defined as described above, there exists an orthonormal matrix W Z such that(P k Z ) T -(P k Z ) T (W Z ) T ≤ 2 E Z δ k (Y )This in turn impliesP k Z -W Z P k Z ≤ 2 E Z δ k (Y )Next, we obtain a result on the projection of a random vector on a k dimensional subspace.Now, we derive a strong bound for P k M e where e ∈ R d is a coordinate wise independent random vector with mean 0 d and M is any d × n a non-negative matrix. We essentially show that for any P k M e = O( √ k) even though e = Ω( √ d) with high probability. Here an important condition to be satisfied is that M and e are independent.Then the projection matrix P k M is a set of k-orthonormal unit vectors p t , 1 ≤ t ≤ k. Then the length of a projected vector P k M e can be written down asP k M e 2 = k t=1 (p t ) T e 2Here one can do an entry-wise analysis of the terms (p t ) T e 2 but that forces a bound of the form that P k M e ≤ √ k(σ + 16 log(nk)) with probability 1 -O(n -3 ). Instead, we recall a result from the Vu [VW15] .). There are constants C 0 , C 1 such that the following happens. Let e be a random vector in R d such that its coordinates are independent random variables with 0 mean and variance σ 2 . Assume furthermore that the coordinates are bounded by α in their absolute value. Let H be a subspace of dimension k and let Π H (e) be the length of the orthogonal projection of e onto H. Then for any n we havePr Π H (e) ≥ σ √ k + C 1 α log n ≤ n -3Now, let us consider the case where H is the subspace covered by the top k many orthonormal eigenvectors of M , denoted as p t , 1 ≤ t ≤ k. Then the projection of e onto H can be written as k t=1 p t , e p t . Then we have(Π H (e)) 2 = k t=1 p t , e 2 = k t=1 (p t ) T e 2. This is exactlyP k M (e) 2. Summarizing, we get the following result with respect to the matrix Z. Corollary B.10. Let P k Z be as defined above. Let e be a d-dimensional random vector with each entry having zero mean and variance at most σ 2 . Then with probability 1 -n -3 we have,P k Z (e) ≤ σ √ k + C 1 • α • log nWe are now in a position to obtain our preliminary pots PCA distance bounds when the projection dimension is k -1.Preliminary intra-community bounds: We start by obtaining the post PCA distance Π k-1 Y (y iy i ) where both y i and y i belong to the same community V j . Lemma B.11. Let y i and y i be two columns of the data matrix Y belonging to the same community V j . Then for some constants C 1 we haveP k-1 Y (y i -y i ) ≤ 2 √ 2 Z -Z • y i -y i δ k-1 (Y ) + 2 √ 2 σ √ k + C 1 • α • log n (5)with probability 1 -O(n -3 ).Proof. Initially we haveP k-1 Y (y i -y i ) = √ 2 P k-1 Z (y i |0 n -y i |0 n ) .Here we use the facts that the spectral projection operators due to Z and Z are close up to some orthonormal rotation and that Z and y i -y i are independent. Furthermore y i -y i = c j +e i -c X -c j -e i +c X = e i -e i , where c X is the centering vector which is a zero mean random vector.Then we have for any k -1 dimensional orthonormal matrix W ,P k-1 Z (y i |0 n -y i |0 n ) ≤ (P k-1 Z -W P k-1 Z )(y i |0 n -y i |0 n ) + W P k-1 Z (y i |0 n -y i |0 n ) ≤ P k-1 Z -W P k-1 Z • y i |0 n -y i |0 n + W P k-1 Z (e i |0 n -e i |0 n ) ≤ P k-1 Z -W P k-1 Z • y i |0 n -y i |0 n + W P k-1 Z e i |0 n + W P k-1 Z e i |0 nFrom Theorem B.8 we have that for a choice ofW P k-1 Z -W P k-1 Z ≤ 2 Z-Z δ k-1 (Z) = 2 Z-Z δ k-1 (Y ).W P k-1 Z e i |0 n + W P k-1Z e i |0 n as Z and the vectors are independent of each other. Then applying Corollary B.10 with probability 1 -O(n -3 ) we have W P k-1Z e i |0 n + W P k-1 Z e i |0 n ≤ 2σ √ k -1 + 2C 1 √ log n.This completes the proof.Preliminary inter-community bounds. Now, we move to the inter-community results. In this part P k-1 Z plays an important role. This is because as per our discussion P k-1EQUATIONUsing this result we then prove the following inter-community post PCA bound. Lemma B.12. Let y i , y i be two columns of the data matrix Y so that i ∈ V j and i ∈ V j , where j = j . Then for the constant C 1 we haveP k-1 Y (y i -y i ) ≥ √ 2 c j -c j -2 σ √ k + C 1 • α • log n - 2 Z -Z • y i -y i δ k-1 (Y ) (7) with probability 1 -O(n -3 ).Proof. As before we haveP k-1 Y (y i -y i ) = √ 2 P k-1 Z (y i |0 n -y i |0 n ) .Then we proceed with a basic decomposition. We have for any k -1 dimensional matrix W ,P k-1 Z (y i |0 n -y i |0 n ) ≥ W P k-1 Z (c j |0 n -c j |0 n ) -W P k-1 Z (e i |0 n -e i |0 n ) -(P k-1 Z -W P k-1 Z )(y i |0 n -y i |0 n ) Now, we have W P k-1 Z (c j |0 n -c j |0 n ) = P k-1 Ȳ (c j -c j ) = c j -c j .Next from Lemma B.11 we haveW P k-1 Z (e i |0 n -e i |0 n ) ≤ 2 σ √ k + C 1 √ log n with proba- bility 1 -O(n -3 ).Finally from Lemma B.11 we know we can upper bound(P k-1 Z -W P k-1 Z )(y i |0 n -y i |0 n ) with 2 Z-Z δ k-1 (Y )• y i -y i , which completes the proof.At this point, we have obtained the pairwise post-PCA intra-community and inter-community distance bounds in terms of y i -y i , Z -Z , k, σ and δ k-1 (Y ). Here δ k-1 (Y ) is the spectral gap of Y and we already have bounds on y i -y i . Next, we obtain bounds on Z -Z and then put together the results obtained so far to prove Theorem B.1.First, we note down a result by Vu [Vu18] for upper bounds on the spectral norm of random matrices with independent entries. Theorem B.13 (Norm of random symmetric matrix [Vu18] ). Let E be a n × n random symmetric matrix where each entry in the upper diagonal is an independent random variable with 0 mean and σ variance, then there is a constant C 0 such thatPr E ≥ C 0 σ √ n ≤ n -3where σ 2 ≥ C 1 log n n . However, since the entries of Y are not independent, the same follows with E Z . To bypass this issue we define the matrix B := 0 X X T 0 and thenB := E[B] = 0 X XT 0 Furthermore recall that E M = M -E[M ].Then we have the following results.1. E Z is the largest eigenvalue of E Z , which is same as the largest singular value of E Y , that we denote as s 1 (E Y ). 2. E B is same as the largest singular value of E X , that we denote as s 1 (E X ).Furthermore we have from Theorem B.13 that E B ≤ C 0 σ √ n with probability 1 -O(n -3 ). Finally we connect s 1 (E Y ) with s 1 (E X ). To do so, note that E Y is the centered matrix of E X . This follows from the fact that E Y = Y -Ȳ and E X = X -X. Then we use the following result by Hanoine [Han14] . Theorem B.14 ([Han14] ). Let M be a rank m matrix and M be the matrix obtained upon centering, with singular values (in descending order) s 1 , . . . , s m and s1 , . . . , s m-1 respectively. Then for any 1 ≤ i < m we have s i ≥ s i ≥ s i+1 .Using this result we get E Z = s 1 (E Y ) ≤ s 1 (E X ) ≤ E B Now, we bound E B , i.e. 0 E X (E X ) T 0 . This is a (d + n) × (d + n) randomFrom Lemma B.2 we have the lower bound on the intra-community distances and upper bound on the inter-community distances. Similarly, we can also use the results to obtain lower bound for the intra-community case. It is easy to see that if (i,i') belong to the same community V j then withprobability 1 -O(n -3 ), y i -y i ≤ 2dσ 2 j + 12α √ d log n.Substituting this and the bound on Z -Z to Lemma B.11 we have with probability 1 -O(n -3 )P k-1 Y (y i -y i ) ≤ 2 √ 2   σ √ k + C 1 • α • log n + N • 2dσ 2 j + 12α √ d log n δ k-1 (Y )  Similarly for the inter-community with i ∈ V j , i ∈ V j from Lemma B.12 we haveP k-1 Y (y i -y i ) ≥ √ 2   c j -c j -2 σ √ k + C 1 • α • log n - N • c j -c j 2 + d(σ 2 j + σ 2 j ) + 12α √ d log n δ k-1 (Y )  Finally, using the bounds of Lemma B.2 and applying a union bound on the total n 2 pairs of datapoints completes the proof of the theorem.The primary quantity that is hard to interpret in a dataset with an underlying community structure is δ k-1 (Y ). Here we make some observations. First note thatδ k-1 (Y ) = s k-1 (Y ) -s k (Y ). Now, s k-1 (Y ) ≥ s k (X) and s k (Y ) ≤ Cσ √ d + n where the latter term comes from the fact that s k (Y ) ≤ E Y ≤ E X ≤ Cσ √ d + n.This follows from a simple application of Weyl's inequality and the effect of centering on eigenvalues. For simplicity, we consider the case when s k (X) ≥ 4Cσ √ d + n. We will come back to this and show that this assumption does make sense. Then, we haveδ k-1 (Y ) ≥ 0.66s k (X). Next note that s k (X) ≥ s k (E[X]) -E .This then implies that given the aforementioned conditions, we haveEQUATION) where E[X] is the center matrix, where each column is the center of the community the corresponding point belongs to.Bounds on the singular values of the center matrix for γ-spatially unique centers Here, we make a connection between s k (E[X]) and the notion of spatially unique centers.Given a n 1 × n 2 matrix M , we define the minimum hyperplane distance, dist M asdist M = min j min v∈Span(M-j ) M j -vwhere M j represents the j-th column of M and M -j denotes the set of all columns of M except the j-th one.That is, it denotes the minimum distance between a data point and the span of the rest of the data points.We have the following classic result of matrix theory.). For any n 1 × n 2 matrix M , the smallest singular value s min (M ) is lower bounded by 1√ n2 • dist M .Now, this result does not directly help us as E[X] has multiple identical columns (it is after all a d × n rank k matrix) and we only get a lower bound of 0. However, we can do a simple two-step analysis to get something nicer.Consider the matrix Ĉ which contains k columns that are each copy of one of the centers of X. Then from the definition of γ-spatially unique centers, we immediately have the following. Fact C.2. If X comes from a setup with γ-spatially unique centers thens k ( Ĉ) = s min ( Ĉ) ≥ γ √ k .Next, let the size of the underlying communities in X. Then we know that E[C] has at least min j |V j | many copies of Ĉ in it (along with other columns corresponding to the larger communities). That means that the singular values in E[X] is at least min j |V j | times the singular values in Ĉ. This gives us the following result.Lemma C.3. Let X be generated from γ-spatially unique centers and let the minimum size of the underlying communities be Ω(n/k). Furthermore, assume s k (X) E X . Then we getδ k-1 (Y ) ≥ C•γ √ n kfor some constant C.Proof. This simply comes from putting the bounds on Ĉ and multiplying them with min j |V j | and then connecting it with Equation 8. Now, to go back to the assumption of s k (X) ≥ 4Cσ √ d + n, consider that n = Ω(d) (this is where will work from hereon), then the assumption holds as long as γ ≥ σk. Now, once we have this result, we can then obtain our main Theorem C.4 in the setting of Spatially unique centers.Theorem C.4 (Relative compression with spatially unique centers). Let X be a d × n dataset k many γ-spatially unique centers where the size of the smallest community is Ω(n/k). Then there is a constant C 1 such that for all intra-community pairs in V j , the compression ratio is upper-bounded as∆ X,k-1 (i, i ) ≥ σ j √ d C 1 σ √ k + α √ log n + 2σ•σj •k √ d γ (9)Similarly for any i ∈ V j and i ∈ V j , the inter-community compression ratio is upper-bounded asEQUATION)with probability 1 -O(1/n).Proof. For simplicity of the statements we have made several assumptions, most of them to consider the harder setting (heavy noise). That is, σ 2 j d = Ω(max j c j -c j ). Furthermore, we assume σ is sufficiently large so that σ 2 d ≥ 100α √ d log n (this happens as long as α = o(d 1/4 )). This implies that the pre-PCA intra and inter-community distances are Θ(2σj √ d) and Θ σ 2 j + σ 2 j √ d respectively.Next, in the intra-community compression ratio bound we have the term2N • σ 2 j d + 12 √ d log n δ k-1 (Y ) = 2σ √ d + n • σ 2 j d + 12α √ d log n 0.25γ √ n/kHere recall that we assume n = Ω(d) which implies 2σ√ d + n ≤ Cσ √ n for large enough n. Furthermore, 12α √ d log n is dominated by σ 2 j d. Combining we get 2σ √ d + n • σ 2 j d + 12α √ d log n 0.25γ √ n/k = Cσ √ nσ j √ d • k 0.25γ √ n = 8Cσσ j • k • √ d γ Similarly the bound 2σ √ d + n • c j -c j 2 + 2(σ 2 j + σ 2 j )d + 12α √ d log n δ k-1 (Y ) can be simplified to C σ 2 j +σ 2 j k √ d γCombining these bounds directly gets us result.Then, Theorem 2.5 is immediately implied, as follows.C.1 Proof of Theorem 2.5We know that γ ≥ C max{σ √ kd 1/4 , σ √ k + α log n}. Furthermore, we assume max i,j c i -c j σ √ d, which is the heavy noise setting. The other case follows the same way. Let C > 100C 1 .Furthermore, note that c i -c j ≥ γ.2σ • σ j • k √ d γ ≤ 0.01σ j √ kd 1/4Similarly, we haveσ 2 j + σ 2 j • k • √ d γ ≤ 0.01σ √ kd 1/4Then, the denominator of the lower bound on the intra-community compression ratio is upper bounded by 0.02σ √ kd 1/4 , and the denominator of the lower bound on the inter-community compression ratio is lower bounded by c i -c j -0.02σ√ kd 1/4 ≥ 0.98σ √ kd 1/4 .Then, the intra-community compression ratio is lower bounded by 10√ k √ d 1/4and the intercommunity compression ratio is upper bounded by 0.05√ k √ d 1/4, obtaining the separation described in the Theorem 2.5.Having discussed the compression ratio bounds in the context of γ-spatially unique centers, we continue with the theoretical support for our outlier detection method in the random-mixture-outlier model. We recall the definition of this model for ease of exposition.Definition C.5 (Mixture model with outliers (revisited)). Let X be a d × n dataset with the partition V 1 , . . . V k , V , a set of k centers {c j } k j=1 and distributions {D (j) } k j=1 +1 with the following generation method. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: We describe the computational environment and running time used to generate the results in the first paragraph of Section 3.• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We have read and understood the guidelines Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer:[NA] Justification: Our work focuses on understanding structures of graphs that appear in real-world data, and our application is focused on clustering of single-cell RNA sequencing datasets. As such, we do not see any immediate negative societal impact of our work. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not see any immediate risk of misuse of our work.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We use publicly available datasets and cite them.• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.From hereon, we use the word community to refer to the underlying structure of the data, whereas clustering of data refers to the outcome of a particular clustering algorithm on the dataset. 
 
 Appendix:  


Decision: The paper had 3 weakly positive reviews, and 1 negative review. The negative review seems most influenced by the fact that the method doesn't work well in low dimensions, but the authors point out they explicitly target the high-dimensional case and provide clear examples of high-dimensional data.  Ignoring the lowest review (as an "outlier"), the paper's average score is still just below the typical cutoffs for a target 20% to 25% NeurIPS acceptance rate. This is just to say that the reviewing process found this paper borderline. Unfortunately the reviewers were not too active in discussion after the rebuttal period.

Hence, the AC read the paper to form their own opinion. At a high-level, this simply seems like a good paper. It has theory and experiments. The theory makes assumptions, as most theory does, but the authors are pretty good about discussing these assumptions and limitations, and include artificial simulations to test the method under different levels of noise-to-separation. Ultimately the real-world experiments, comparing with a very reasonable set of alternative methods, show that the method does well in the type of biological data problem considered, which somewhat validates the assumptions.

I don't see any major flaws, and I like the contributions: some theory, and a new practical method (very simple, and the only parameter is the number of outliers). This reminds me of k-means (ie., Lloyds algorithm) itself: there have been hundreds of papers that propose methods to improve on k-means, but everyone still uses vanilla k-means because it's simple, not-bad, and time-tested. So there's a lot to be said for simple methods, especially when there is some kind of theory behind it.

Thus I'm happy to recommend acceptance.

I do have a few minor comments which I encourage the authors to address, in addition to any remaining issues raised by reviewers.
-  "… K-Means, which is also known as spectral clustering."  The structure of the sentence made this vague, but if you are saying that reducing dimension with PCA and then doing k-means is the same as spectral clustering, I disagree. For spectral clustering, k-means is done on the eigenvectors themselves, not after applying the eigenvectors to the data. Furthermore, spectral clustering has an explicit metric or graph structure leading to an explicit graph Laplacian, which is then used for the eigendecomposition. For PCA, it can be thought of as either doing the SVD on the data, or the eigendecomposition of the Gram matrix. But even if you think of the Gram matrix as the graph Laplacian, I think it's still distinct from the usage you have in mind.   I think I'm right, but regardless of whether I am right or wrong about this, this connection needs more explanation.
- I assume that these new outlier methods outcompete old standards, such as DBSCAN (which clusters and finds outliers at the same time), right?
- Line 150 mentions $d \ge 10 \alpha \sqrt(d) \log n$, but should that $d$ on the RHS be $n$?
- Line 171 mentions "Equation (9)" which I can't find.  
- Fig 1b goes into margins. In general I don't mind, but out of fairness to other submissions that kept within margins (and had to cut material to do so), I think it was a little unfair. At this point, after acceptance, I don't think it needs to be fixed though (unless someone else complains).

Reviews: review: paper_summary: paper_summary: The paper proposes a new measure called ‘compression ratio’ to determine how effectively PCA compresses data. For subspace clustered data the authors show that if the signal directions for each cluster are well-separated, the compression ratio is larger for within clusters than compared to between clusters. The paper also proposes a method for outlier detection through this compression ratio.
strength_weakness: strength_weakness: 1. The assumptions in the paper are quite strong in my opinion. Especially the assumption of nearly orthonormal cluster centroids is unrealistic for low-dimensional data ($n \gg d$) where PCA is usually applied.

2. The outlier detection algorithm requires a run of the PCA to find the compression ratio. However, it is well known that PCA is not at all outlier robust. In that case how are the compression ratios reliable? The theoretical guarantees in Theorem 2.8 does not seem to match this intuition. Is this guarantee only an artefact of the restrictive assumption on the subGaussianity of the outliers?
questions: questions: 1. Usually, it is common practice to calculate the information lost in PCA based on the ratio of the sum of the eigenvalues. How does the compression ratio relate to the variance explained? A clarification regarding this is warranted.
2. How do the authors manage to run vanilla PCA on single-cell RNAseq data on which $d \gg n$? Do they use a different version of the PCA? 
3. How does the method compare to other robust PCA techniques?  What are the advantages of their proposal compared PCA-based custering methods such as IF-HCT-PCA? 

Jiashun Jin. Wanjie Wang. "Influential features PCA for high dimensional clustering." Ann. Statist. 44 (6) 2323 - 2359, December 2016. https://doi.org/10.1214/15-AOS1423

Also see my questions in the weakness section.
limitations: limitations: Yes, limitations are discussed.
paper_summary: paper_summary: This paper studies the denoising effect of PCA  using a novel metric called "compression ratio". The metric is defined as the ratio of the pre and post-PCA between two points. The authors note that when the dataset has a community structure, outlier points tend to have a flatter distribution of compression ratios w.r.t other data points, whereas inlier points have a larger compression ration w.r.t to other intra-community data points. This insight is used to design a simple outlier-detection algorithm for data with community structure. Under certain assumptions on the data distribution, the authors show that this outlier identification algorithm succeeds with a constant probability. The authors also provide many experimental results on both synthetic and real-world datasets to show that their proposed methods outperform existing algorithms.
strength_weakness: strength_weakness: - Because of the theoretical nature of the paper, there are many assumptions such as knowing the number of outliers, and assumptions on the noise distribution. These assumptions do not always hold in real-world data.
questions: questions: - In Figure 1, it seems like the proposed method (Variance of compression) performs worse than most other methods. Can the authors provide more information regarding Figure 1b? 
-
limitations: limitations: See questions and weaknesses.
paper_summary: paper_summary: This paper introduces compression ratio, defined as the ratio of pre-and-post-PCA distances for a pair of observations, for outlier detection tasks. The authors demonstrated that this metric could capture the effect of PCA on high-dimensional data with moderate noise and proposes that points with lower variance of compression ratio and do not share a common signal with others are more likely to be outliers. The proposal was validated in both simulations and on real-world scRNA-seq datasets.
strength_weakness: strength_weakness: 1. More robustness/sensitivity analysis would be needed to help understand how widely applicable this simple ratio is. 
2. The current real data application is not well-motivated: while identifying potentially mislabeled cell types are interesting, these are often better treated as deconvolution and/or mixture model problems.
questions: questions: 1. In Figure 1, why is the variance of compression achieving moderate to low ranks? 
2. The simulated outliers seem to come from a convex combination of existing clusters — have the authors considered more general outlier cases?
3. I would encourage the authors to provide more simulation results with higher dimensionality (right now it uses d=1,000 < n=3,000)?
4. On the selection of dimension for PCA, it looks like choosing anywhere from k to 2k (where k is the true number of “community”) is not too bad — in practice is there any advice and guidance on choosing k in the first place that performs reasonably?
5. From Algorithm 1, it seems like returning these indices requires at least doing O(n^2) distance after performing PCA — adding the theoretical and empirical time complexities on some of these datasets would benefit this method's users. 
6. I would encourage the authors to compare the results on benchmark datasets used for outlier removal, especially since that is the primary application highlighted.
limitations: limitations: Detailed in questions.
paper_summary: paper_summary: In this paper, the authors propose a novel metric called compression ratio to capture the effect of PCA on denoising which can significantly reduce the distance of data points belonging to the same community while reducing inter-community distance relatively mildly. They try to explain this phenomenon through both theoretical proofs and experiments on real-world data. In addition, they design a straightforward algorithm that could be used to detect outliers and provide many experimental results to demonstrate its superiority over existing methods.
strength_weakness: strength_weakness: The paper only conduct experiments on single-cell RNA-seq, which is not convincing. Results on more datasets are expected.
questions: questions: Can more metric comparison be included such ARI?
Table 3 the middle 2 columns (Purity) they are the same, I guess one is 5% and another one should be 10% instead of 5%?
limitations: limitations: NA

Comments: title: Response to Authors
rebuttal?
comment: As we mentioned in our paper (even abstract, first sentence of the second paragraph), our main focus in this paper is high-dimensional noisy data. Here $k$ is the number of clusters and $d$ is the dimension of vectors. In single-cell data, $k$ is usually smaller than $50$ and $d$ is usually larger than $20000$. For another example, in popular image data sets such as MNIST and F-MNIST, $k=10$ and $d=784$. The condition $d\gg k$  is also true for many many other domains. 

In the case of $k\geq d$, we  believe PCA or spectral algorithms are not the correct approaches. For example, many spectral algorithms (including PCA) projected the high-dimensional data into $\Theta(k)$ dimensional vectors in applications to data/models with $k$-clusters. If $k\geq d$, we believe the projection will remove some useful information. See the link for spectral clustering https://en.wikipedia.org/wiki/Spectral_clustering .

If the reviewer insisted that our algorithm failed in low-dimensional data, then we agree with the reviewer and have nothing to discuss with, since $k\geq d$ is not in our consideration.

Also, in the entirety of our paper, we only say that our algorithm is robust under the choice of the projected dimension, and it is very different from the concept of robust PCA. Using the compression ratio of PCA as an outlier detection algorithm has no connection to robust PCA. We are not sure why the reviewer connected our result with robust PCA. Please see the link of robust PCA (https://en.wikipedia.org/wiki/Robust_principal_component_analysis).
Thank you for the detailed rebuttal. However, I still have some reservations regarding the assumptions as they are quite strong and does not hold for practical senarios. For example the assumption won't hold for $k > d$. Additionally, if I understand correctly, the subgaussianity of the outliers appears to be crucial for the theoretical guarantees, potentially excluding cases with unboundedly large outliers. This undermines the purpose of developing of being outlier-robust. Please correct me if I’m mistaken.

Given that the paper also proposes an outlier-robust PCA and evaluates its effectiveness through clustering performance, I believe it should be compared with similar recent methods, such as IF-HCT-PCA and other robust PCA techniques. Unfortunately, the current experimental setup does not seem to address such comparisons.

Thus, I am inclined to keep my scores as is.
Dear authors (and reviewers),

This paper has split reviews, all close to the border between acceptance and rejection. A lot of NeurIPS submissions fall into this category, and if there's no strong rebuttal, usually these papers end up being rejected.

So I highly suggest the authors write a strong rebuttal to each of the reviews. (If you don't think this is possible, you can choose to withdraw the paper). If you think the reviewers were not clear enough in their criticism, you can always ask them to elaborate.

Reviewers, please read each others' reviews (and the rebuttals when written). As a reminder to everyone, the OpenReview platform allows us to have a dialogue, so you can post small questions/comments and responses at any time.

Best, Area Chair