Capturing the denoising effect of PCA via compression ratio
Authors: Chandra Sekhar Mukherjee
Nikhil Deorkar
Jiapeng Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: PCA
Compressibility
Heavy tailed noise
clustering
outlier detection
Primary area: interpretability_and_explainability

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.

Capturing the Denoising Effect of PCA via Compression Ratio
Chandra Sekhar Mukherjee chandrasekaar.uukhrjeeee usc.edu
Nikhil Deorkar deorkar@ @usc.edu
Jiapeng Zhang jiapengz@ usc.edu
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, improvement of noisy data is still not well quantified in general.
In this paper, we propose a novel metric called compression ratio 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 straightforward algorithm that could be used to detect outliers. Roughly speaking, we argue that points that have a lower variance of compression ratio do 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 clustering algorithms. Our method is very competitive with popular outlier detection tools in this task.
Introduction
Principal component analysis, commonly known as PCA, is one of the most fundamental tools in machine learning. PCA is primarily used as dimensionality reduction tool that transforms high- dimensional data to lower dimensions for better visualization as well as a heuristic that reduces the complexity of the algorithms that are to be run the data. On the other hand, it is also known to have certain denoising effects on high- high-dimensional data. This denoising phenomenon has been observed in different domains, including biological data [K [KHH19] VKS17), speech data (Li18). signal measurement data (A 19 image data MBSP12] among others. The denoising effect of PCA has been extensively studied over the last decades And58 HR03 Dac05 RVdBB96 Nad08
Nad14 14, /N17 MZ23 MZ24].
"Thomas Lord Department Computer Science, University of Southern California. Research supported by NSF CAREER award 2141536.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

One of the most fundamental problems in unsupervised learning is the analysis of data in the presence of community structures [CA66]. This includes clustering of such data [XT15], visualiza- tion [WT21] 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] [K TO [SS2),, where PCA in combination with a K-Means based iterative algo-
rithm is shown to provide a good clustering of that dataset with mild assumptions with the underlying community structure.
However, PCA seems have more "general" denoising effect data, as it improves the performance of various downstream algorithms. including clustering [VKS17] as well community structure preserving graph embedding [HHAN and this denoising effect is evident many real-world datasets.
1.1 Contributions
To this end, we propose metric, called compression ratio, that quantifies PCA's improvement of high dimensional noisy data with underlying community structure in a geometric, and thus algorithn-independent manner
Compression ratio. Let u and v be two data points from dataset and let 1I, be the t-dimensional PCA projection operator. Then the compression ratio between the two points is defined the ratio between their pre-PCA and post-PCA distance, which is
uu - mll [11, ( - (1)
In a dataset with community structure, we show the compression ratio for intra- corma-ctmmuityy pairs is higher than that of inter- cotmuncym pairs even in settings where the pre-PCA inter-communig and community distances are very similar. We demonstrate (through random vector mixture model) that this ratio gap reflects the denoising effect of PCA. As consequence, PCA brings points from the same community much closer, improving the performance of downstream algorithms such as K-Means.
As motivating byproduct, we show that this metric can be used to design an outlier detection method that can detect points deviating from 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 extension of the standard random vector mixture model. We also compare our algorithm with popular algorithms such as the Local Outlier Factor (L.OF) method [BKNSOO] and KNN-dist (RRS00) well as recent methods such Isolation for- est [LZ008] and ECOD 2 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 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 single-cell data, as it is both high dimensional (20, 000 40, 000 dimension) and noisy [AH19), 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
è 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 particular clustering algorithm on the dataset.

---

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-Meanm 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 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 we demonstrate that PCA exhibits an average version of compression ratio in real-world biological datasets [DRS20] and then test our outlier detection- baased clustering accuracy improvement idea discussed above.
1.2 Related Works
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] RVdBB%6 HR03] [acO5] and the references therein). In the last two decades, several works have also considered the finite sample setting [Na008] 4 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) aub-Gaussian noise. However, there seems 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 Gabssaassian.
PCA in clustering tasks 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 [DH4] showed that the outcome of PCA can be viewed an approximation result 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 discuss here, which was then improved in [AST2]. Both of the works focused on the setting of n >> d (for example, [K10) worked with n 2 d²). More recently, tighter results have been obtained in the context of the
model in [ZZI (still on the setting of n >> d²).
In comparison, we study PCA's relative compression in an algoritmm-independen fashion, focusing on its effect on the geometry of the data in the high-dimensional setting of n s2(d) with sub-Gaussian noise. We are motivated analyze this setting as single-cell datasets often have n < d.
2 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 in [KK10 AS12). We call this random vector mixture model. This also be interpreted as a signal-plus-non data. The dataset of interest is a of n many d dimensional real vectors x; R 1 which is together represented as the dataset X. We express X as a d x matrix, with each column representing data point. The data points have an underlying hidden community structure that is expressed as a partition of [n] := {l...., n into & many sets Vi...., V₂ such that each i E [n] lies in any one Vy. We then have the following problem structure.
model where the signal imposes a community structure on the n,
1. Each cluster Vg. 1 j S l is associated with a ground truth center cj Rdd.
2. Additionally, each cluster V, is associated with a distribution DG) such that D(j is a coordinate wise independent zero mean distribution. For case of exposition, we define the support of D(i) to be [-a, ad for some (which can also depend on n. d), but our methods also directly apply to sub-Gaussian distributions where each coordinate has constant sub-Gaussian norm (resulting in ((vd) norm of any column vector). Then a would be replaced with C" log n for some constant C' in our bounds.
3

---

Then, the dataset X is set up follows.
Definition 2.1 (Random vector mixture model). For each E [n|] if E Vj, then æ; Cj + where e ~ D(2), i.e. 6s is independently sampled from DG), Here we abuse notation and denote both E Vj as well ma E Vj-
With this setup, now we define the PCA projection operator and the compression ratio metric formally. Definition 2.2 (The PCA operator ITx) ). Let X be d x 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, 2") we define the k--PC compression the pair of vectors in X as
|| 3g/ (x, | (a4) 11 (<+)
Before describing our results, we define certain parameters of the model.
1. The maximum variance of the entries, is defined as x² maxigissasesd VarlD
2. The average variance of column in a distribution D(), noted as ar is defined as of
1 E, Var([D)))) Here, ory v is the perturbation on the data points of Vj 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 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.I
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 restricted (still natural) structure on the centers, which allows us to give more interpretable result in this case. For simplicity, we also work in the setting where d 2 10a Iol log n.
Definition 2.4 (Spatially unique centers). We say set of vectors C {c....., ck} are 7-spatially unique, if we have that
min ISick vESpan((*(e))
min
|cg
v/ 2
This implies that each center has a unique pattern that cannot be approximated by a combination of the other centers. Here note that 7 minjyd' ||cj - clr For example, such 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 cntrr-community compression ratios of PCA.
Theorem 2.5 (Separation of compression ratio). Let 7 C max(ookdd ovk + log n for some constant C. Furthermore, let i' denote that yi and y 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.
2. With probability (1/n)), min I (i, 2 4- (aX Ax 1i, (i)
This shows that the compression ratio of PCA provides 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 more general theorem w.r.t spatially unique centers in Theorem C.4
natural question is whether post-PCA distance is 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 jj. communities with larger variances have larger intra- community distances. However, this gets normalized in the compression factor as per Equation (9) of Theorem C.4, as the numerator also has a dependency Tj..

---

Algorithm Outlier detection via variance of compression ratio
Input: data X, PCA dimension k', number of outliers
for i = ri do SC <- VARAx,u (VARAx,, x defined in Eq.
end for return many indexes with lowest SC' values.
2.1 Outlier detection with compression ratio
Now, 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 E X is defined
VARA x (x:)
(1,
| where (i,' = |n (w.) 11 (=,()
the compression ratio between points and i'.
That is, simply the variance of the of compression ratios of æ; with the other points xy-
Then, our intuition that if data consists of many points from the high dimensional mixture model, well several outlier points that don't share common signal (center), they have lower variance of compression ratio. We concretize this notion with the following simple detection algorithm !
Mixture-model with outliers Now let consider an extension of the mixture model in Defini- tion 2.1 to incorporate outliers.
Definition 2.7 (Mixture model with outliers). Let X be a x n dataset with the partition Vi...., V2, V, a set of le centers {c;}/=1 and distributions (D(i) ) + 1 with the following genera- tion method.
1. clean points: If V,,15 S Cj es where ej is sampled from D)5),
2. outliers: i E V, then we sample pi,1,..-PPay E [0.5, 1]. Then u, = E3 oz + where pi.j and e is sampled from (I++1),
0ijj = Eis Fi.
Let |VI n. and n. + ne. To keep the results simple, make the average variance of each distribution D(O same, which o'.
Such a scenario can occur in many different settings. For example, consider single-cell datasets which a popular biological data type. Here each data point is 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 [THL" + 19 VKS17 KAH19] Although the gene expressions within popullatoll should have similarities. they are perturbed by biological and technical noise, making high- nigh-dimensional mixture models good setup to study them. However, some cells may belong any particular sub- cobpoopulations, but rather be intermediate cells. Additionally, sometimes cells get merged during the biological experiment that records the gene expressions, generating data points that behave like a random mixture of two or more data points. Our model aims to model such scenarios.
In this setting, we get the following outlier detection result where the centers have spatially unique centers.
Theorem 2.8 (Outlier detection via Algorithm D. Let X be a x n dataset with 7-spatially unique many centers where logn < < /d and no outliers in the setting of Definition 2.7 Let the following conditions hold
1. |c; -yyll =
=O(o'va Vd) (the noise is significant)
2. 7 2 3/2 /o' k. l logn
5

---

Then, for any S n,2, the first points ranked by Algorithm aall belong to the outlier group (V) with probability (1))
We discuss the connection between 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 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, simulations of our model to test the efficacy of our outlier detection method and its impact on the community structure 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 MI 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-c;]l c. set the noise distributions to be Bernoulli distributions with variance σi, 02 0g respectively. We work in two primary settings, of equal and unequal noise.
Equal noise. Here we have o, = for all i. Un)uuul noise. Here of the communities has variance 20, whereas all the other communities have variance a.
Then, test the algorithms for three values of a in the following manner.
Low noise: We choose o ||q Cy /d. This implies distance between the centers dominates the perturbation due to noise.
Significant noise: Here ||e] Cy || R vvd. Here the noise norm and distance between centers are of the same order.
High noise: We have a
||q cy x 0.3o vd. 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 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 the high-noise setting, there now an overlap between intra-community and inter- citer-community compression ratios. We demonstrate this in Figure Ta This further indicates that compression ratio indeed useful metric even when the noise has 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).
Compresaiiily Durves
Variance based cutiers with unequal noise levels
Compression
30-
LOF
AUROC Score
2.8
KV/- dizz
3.8
KNN
Iso ebon Fores:
0.8
PCA + Isolation Forest
0.-
ECOD
PCA + ECOD
commmnntty en/2
0.-
High
(a) Comparing intra and inter community compression ratios in simulation
(b) AUROC of variance-based outlier removal
Figure 1: Simulation results for compression ratio and outlier detection

---

3.1 Outlier detection
Now, we discuss the outlier detection, starting with the simulation setup in this case. We follow the random- cislommmixture-outiic model and add outlier points along with the clean points as follows.
We add n, n../ nz/10 10 outliers following definition 2.7 That is, randomly choose ....... at and then random mixture-center is chosen as Σ, 0r and then we add random noise vector from the Bernoulli distribution of variance 04.
Outlier detection algorithms for comparisons Outlier detection has been an active area of study in unsupervised learning, providing several influential algorithms. In 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 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 [LT708] and also very recent and popular outlier detection method ECOD 22) We also use PCA+method for each of the methods as benchmarks, as both outliers and clean points perturbed by zero-mean noise, and we now understand PCA can help mitigate the effect of said noise, as discussed in Section
Outlier detection results We compare the AUROC values of the 5 outlier methods of interest in these settings. We record the results in Figure and 2b for the equal and unequal noise settings respectively.
Ranskem-rritu cutlans with aqual razie lovel
Randamm-nitture aztler with uraqu naka levels
Compersttoo
Lor
KNN dit
AURDC
PCA i Rutledis
Iolettion Tornet
PCA i boladin Forest
HC3D
ECOC
Low Notse
Sightiicent Nobe
High Noise
LoW
Sign Sign nobe
High nolse
(a) AUROC of outlier removal in equal noise setting (b) AUROC of outlier removal in unequal noise setting
Figure 2: Comparison of outlier removal in different noise settings
As we can see, our method results in the highest AUROC value, followed by PCA+KNN-diss we make two observations.
i) The performance gap between variance-off-omppessii and the next best method is higher in the unequal noise setting.
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 remark that in real- worldworld 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 different kind of outlier, which concretize below.
Higher periance-based outliers 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 a coordinate- wise variance, where c for our experiments (recall that the noise in the other points has a coordinate wise variance). It is well known that if noise 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 more comparable to the other methods. We record the results in Figure lb
7

---

Datnset
intercluster
Avg.
intracluster
Avg.
Dataset
NMI PCA
k-means
compression
compression
Koh
0.847
Koh
2.539
7,468
Kumar
0.924
Kumnr
1,969
14.811
Simkumarleass
0.746
Stinkumur-een
3.577
15,808
Simkumurthard
0.237
Simkumarkhard
5.267
15,051
SimkumarShard
0,449
SimkumurShard
4.349
9.370
Trupnell
0.286
Irapnell
6.373
9.857
Zheng44q
Zhengdey
2.399
6.639
Zheng4unes
0.691
Zheng4uneq
2,215
6,260
Zheng8eq
0,354
Zhenggeq
2,398
4,722
Table 2: Average PCA+K-Mennt outcome
Table 1: Relative compression on RNA-seq
before data removal
datasets
This shows that our outlier detection method is adept at detecting different kinds of outliers, outper- forming popular outlier detection tools in some settings, and being competitive 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,
focus real-worls datasets.
4 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 Z 10, 000 genes are recorded. A fundamental problem here to identify sub-populations of interest. However, the problem is challenging as the biological process of recording gene expressions error- prone [THL* 19), and gene expressions within the same population may also vary due to internal randomness. Furthermore, experiments recording [XL2I]. This makes single-cell RNA sequencing data a good testing ground for high dimensional noisy data with outliers and underlying community structure.
cause cells to get merged during gene-expression
In this direction, we consider the single-cell RNA sequencing datasets from a benchmark pa- per [DRS20). These datasets also have moderate to highly reliable ground truth labels, that help us understand the usefulness 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 in Appendix E.T
4.2 Average compression in the datasets
As discussed Section 2 and described Theorem 2.5 our primary result showed that the intra-community compression ratios higher than inter-community compression ratios in large range of parameters. Here we look at average statistics of compression ratio to provide first layer of evidence supporting this phenomenon in real-world data. We define the follow- ing metric. For any community Vj. we define the average intra-community compression ratio as mm merll |ITTy (z: +,,)
intrax (V,) = E.
Similarly, the average inter-community compression ratio
1,''V,
E is defined as interx, (V)) E
| |IT
This gives an average measurement
of the compression ratio in the dataset. this regard, we find that for each of the 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 F.2 Here, for brevity we present the average of intrax (V)(V) and interx.k-11 (V,)) for each dataset in Table
8

---

4.3 Improvement of clustering results via outlier detection
Next, we study the usefulness of our outlier detection method in these datasets. Unlike our simulations there is no -ouuth labeling for outliers. Rather, we assume that in each community (as defied by the labels provided with the dataset), some points may behave more like an outlier, in that they may be mixture of different signals. These can also be points that have uncharacteristicalyy 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 is known to be effective in single-cell datasets VKKS17 KAH19).
Experimental setup For each of the datasets, we do the following. Let i be the number of communities. We apply some c-dimensional PCA and then run 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 starting point. Then, for each dataset, we apply 9 outlier detection methods. The algorithms are our variance-of-compeee and PCA-added versions of LOF, KNN-dist, Isolation forest, and ECOD. We have two settings.
wwtrreoos-oopposooo-oeeeee ratio method, and the original
First, we set k (following our theory), and obtain the initial PCA+K-meam results in Table Then, we remove 5% of the points according to the outlier score and then run PCA+K-Mean 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 e = 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.
Results As 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 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
Averuge Rank
NMI.
NMI,
Purity, dim
Purity
NMI,
Furity. dim Removal
Algorithm
dim k-L.
dim k-
dim k-
dim 2k,
5% removal
10% Remowal
5% Removal
10% Removal
10% Removal
10%
Var. of Compression
2,333
2,333
3,444
2.111
2,889
2,356
LOF
4,222
5.0
3.667
3.444
5,333
6.356
PCA LOF
3,556
4,556
4.22
4,222
3.667
KNN
500
4,333
3.11
3555
3,778
3.444
FCA KNN
4,556
4,556
3,778
3.778
4.667
4,353
Isolation Forest
4,667
6.0
4,333
5.111
5,667
5,222
PCA + Isolation Forest
4,222
4,333
2,444
3.111
4.444
2,667
FCOD
4,889
3,556
3,556
3.111
3,667
3.0
PCA + ECOD
6,333
3.111
4.111
4.607
4,356
4,232
Table 3: Average rank of improvement across all algorithms and experimental settings
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 [.4 of the appendix that the compression ratios of most points change only mildly when > In terms of experiments, we verify it as follows. For k'' 2k, we calculate the average intra-community and cnter-commumity compression ratios in Appendix E..4and and find them to be consistent with Table [ 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 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 suitable choice for different datasets. Another concern is that our outlier detection tool may not be optimal for handling highly unbalanced communities, very small community will show lower variance of compression ratio. These remain interesting research directions. We note more future directions in the Appendix F

---

References
[AM13] Mohiuddin Ahmed and Abdun Naser Mahmood. A novel approach for outlier detection and clustering improvement. In 2013 JEEE 8th Conference Industrial Electronics and Applications (iciea), pages 577-582. IEEE, 2013.
[And58] TW Anderson, introduction multivariate statistical analysis. Wiley google schola, 2:289-300, 1958.
[ARS*04] 04] P. Antonelli, H. E. Revercomb, L. A. Sromovsky, W. L. Smith, R. O. Knuteson, D. C. Tobin, R. K. Garcia, H. B. Howell, H.-L. Huang, and A. Best. principal component noise filter for high spectral resolution infrared measurements. Journal of Geophysical Aimospheres, 109(D23), 2004.
Research:
[AS12] Pranjal Awasthi and Or Sheffet. Improved spectral-norm norm bounds for clustering. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 37-49. Springer, 2012.
[BKNSO0] Markus Breunig, Hans-Peter Kriegel, Raymond T Ng. and Jörg Sander. Lof: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 93 23-104, 2000.
[CA16] M Emre Celebi and Kemal Aydin. Unsupervised learning algorithms, volume Springer, 2016.
[CTP19] Joshua Cape, Minh Tang, and Carey E. Priebe. The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. The Annals of Statistics, 2019.
[DH04] Chris Ding and Xiaofeng He. K-means clustering via principal component analysis. In Proceedings of the Twenty-First International Conference Machine Learning, ICML '04, page 29, New York, NY, USA, 2004. Association for Computing Machinery.
[DK70] Chandler Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[DRS20] Angelo Duò, Mark Robinson, and Charlotte Soneson. systematic performance evaluation of clustering methods for single-cell maa-se data. F1000Reseurch, 7:1 141, 11 2020.
[Han14] Paul Hanoine. An eigenanalysis of data centering in machine learning. Preprint, 2014.
[HHAN 21] Yuhan Hao, Stephanie Hao, Erica Andersen-Nissen William M. Mauck IIII Shiwei Zheng, Andrew Butler, Maddie J. Lee, Aaron J. Wilk, Charlotte Darby, Michael Zagar, Paul Hoffman, Marlon Stoeckius, Efthymia Papalexi, Eleni P. Mimitou, Jaison Jain, Avi Srivastava, Tim Stuart, Lamar B. Fleming, Bertrand Yeung, Angela Rogers, Juliana M. McElrath, Catherine A. Blish, Raphael Gottardo, Peter Smibert, and Rahul Satija. Integrated analysis of multimodal single-cell data. Cell, 2021.
[HHH+22] Songqiao Han, Xiyang Hu, Hailiang Huang, Minqi Jiang, and Yue Zhao. Adbench: Anomaly detection benchmark. Advances in Neural Information Processing Systems, 35:32142 35:32142-32159, -21199, 2022.
[HR03] DC Hoyle and M Rattray, Pca learning for sparse high-dimensional data. Europhysics Letters, 62(1):117, 2003.
[Jac05] Edward Jackson. A user's guide to principal components. John Wiley & Sons, 2005.
[KAH19] Vladimir Yu Kiselev, Tallulah S Andrews, and Martin Hemberg. Challenges in unsuper- vised clustering of single-cell rna-seq data. Nature Reviews Genetics, 20(5):273-282. 2019.
[KHK19] Yasunari Kusaka, Takeshi Hasegawa, and Hironori Kaji. Noise reduction in solid-state nmr spectra using principal component analysis. The Journal of Physical Chemistry A, 113333-11333-10333 2019. PMID: 31682439.
10

---

[KK10] Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In 2010 JEEE S1 Annual Symposium on Foundations of Computer Science, pages 299-308. IEEE, 2010.
[Li18] Bingbing Li. A principal component analysis approach to noise removal for speech denoising. In 2018 International Conference on Virtual Reality and Intelligent Systems (ICVRIS), pages 429 432, 2018.
[LTZ08] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In 2008 eighth ieee international conference on data mining, pages 413-422. IEEE, 2008
[1ZH++22] Zheng Li, Yue Zhao, Xiyang Hu, Nicola Botta, Cezar lonescu, and George H Chen. Ecod: Unsupervised outlier detection using empirical cumulative distribution functions. IEEE Transactions on Knowledge and Data Engineering. 35(12):12111-12119, 2022.
[LZZ21] Matthias Löffler, Anderson Y Zhang, and Harrison H Zhou. Optimality of spectral clustering in the gaussian mixture model. The Annals of Statistics, 2565)22506- 2021.
[MBSP12] Y Murali, Murali Babu, Dr Subramanyam, and Dr Prasad. Pea based image denoising. Signal & Image Processing, 3, 04 2012.
[MZ23] Xinyu Mao and Jiapeng Zhang. On the power svd in the stochastic block model. In shirth-seventh Conference on Neural Information Processing Systems, 2023.
[MZ24] Chandra Sekhar Mukherjee and Jiapeng Zhang. Detecting hidden communities by power iterations with connections to vanilla spectral algorithms. Proceedings of the 2024 Annual ACM-SIA ACM-SIAM Symposium Discrete Algorithms (SODA), pages 879. SIAM, 2024.
[Nad08] Boaz Nadler. Finite sample approximation results for principal component analysis: matrix perturbation approach. The Annals of Slatistics, 36(6):2791 - 2817, 2008
[Nad14] Raj Rao Nadakuditi. Optshrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage. IEEE Transactions on Information Theory, 3000)30183-31
2014.
[RRS00] Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim. Efficient algorithms for mining outliers from large data sets. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages
2000.
[RV08] Mark Rudelson and Roman Vershynin. The littlewood-offord problem and invertibility of random matrices. Advances in Mathematics, 218(2):600 630000663331100 2008.
[RV]BB96] Peter Reimann, Chris Van den Broeck, and Geert J Bex. A gaussian scenario for unsupervised learning. Journal of Physics A: Mathematical and General, 29(13)3552,, 1996.
[THL+19] Xiaoning Tang, Yongmei Huang, Jinli Lei, Hui Luo, and Xiao Zhu. The single-cell sequencing: new developments and medical applications. Cell & Bioscience, 91)):33, 2019.
[TWT21] Francesco Trozzi, Xinlei Wang, and Peng Tao. Umap dimensionality reduction tool for molecular dynamics simulations of biomacromolecules: a comparison study. The Journal of Physical Chemistry B, 125(19):5022-5034, 2021.
[VKS17] K. Kirschner V Kiselev and M Schaub. SC3: consensus clustering of single-cell RNA-seq data. Nature Methods, 14:483-488 2017.
[VN17] Namrata Vaswani and Praneeth Narayanamurthy. Finite sample guarantees for pea in non-isotropic and data-dependent noise. In 2017 55th Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 783-789, IEEE, 2017.
[Vu18] Van Vu. simple svd algorithm for finding hidden partitions. Combinatorics, Proba- bility and Computing, 27(1):124-440, 2018.

---

[VW15] Van Vu and Ke Wang. Random weighted projections, random quadratic forms and random eigenvectors. Random Structures & Algorithms, 47(4):792-877 2015.
[XL21] Nan Miles Xi and Jingyi Jessica Li. Benchmarking computational doublet-detection methods for single-cell ma sequencing data. Cell systems, 12(2): 2021.
[XT15] Dongkuan Xu and Yingjie Tian. A comprehensive survey of clustering algorithms. Annals of Data Science, 2: 2:165-192 2015.
12

---

A Organization of the appendix
In Sectiion B we obtain our first, generic proofs for compression ratio. Next, in Section 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 when number of components is more than h: +
Section CasioonEJoontin contains continuation of experimental results from the main paper. We conclude with some future directions in Section F
B Primary theorem and proof
In this section, describe primary compression ratio related result in the random vector mixture model. We first describe our result when the projection dimension is 1. We first define some notations and useful results that will use.
B.1 Preliminaries
We first define the SVD projection operator for matrix X. Let the k' diddmenssioal SVD projection operator for matrix be Pk
Next, for the dataset matrix X, we denote by its centered version. Then we have 11 = P
| is in fact 11 y. Then the compression ratio of the data pair (i, defined as || (#(-w,))
IP (yx y. yll
Then we have the following bound on the compression ratios in the random vector mixture model.
Theorem B.1 (Main result). Let X be d x n dataset setup the random vector mixture model with k underlying communities, so that all centers ej and all column vectors I; E X are in [-a, a] Let be the corresponding centered dataset. Considering the following notations,
1. 6w (M) == sw (M) - (W++(M)for any M,
2. ²² be the maximum variance of the random variables,
3. N Vo for some constant Co
of 2 C1 logn for some constant C₁ then with probability 1 - ((1/n) we have that the (k PP-PC compression ratio, Ax, of all intra-cluster pairs (i, is lower bounded as
Ax,
2do 12a 12aVologn
2 ovk + C1 a. a. Vlgn
2N
Wo3o4412vvd a 6x-
Similarly, the compression ratio of all inter-cluster pairs (i,i') is upper bounded by
Ax.=-(i,7')
V d(o3 d(o7+03)) +03) +1c, 11 12a
(3)
2N |6 -e, 2 +12 V2 [1q 1log-cyll-2 2 + Vogg+
6 1())
with probability ((1n))
Here we make the following remark about the range of the datapoints.
B.2 Definitions and notations
We start with the definition of the norm operator |]. which we use in the following two contexts.
13

---

1. If u is d dimensional vector, then ||a||| denotes the & norm of u, which is v VE (u;)?
Then l|u bll the lz distance between the two vectors.
2. If M is a d x n matrix M. ||M] denotes the spectral norm of the matrix. That is,
|M
max 26, 2 u [|]
We follow this by defining some more structures related random matrices.
For any matrix M, we denote N7 == [[M]. Then by definition, X is x matrix such that i E Vj, the i-th column of X is og (as D(J) is coordinate wise zero mean distribution), the ground truth center of Vz. Thus, we denote by X as the ground-truth or expectation matrix of X. Similarly Y is the center matrix of Y (recall that Y is the column centered matrix of X). Furthermore let M, be the i-th column of M. Then 1 Te = | Fy for any (i, pair. Thus
call Y as the ground truth matrix of Y.
2. Corresponding to any matrix M, we denote EM == M - E[M].
3. Choice of subscripts: From hereon we use the subscript 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 background, we give 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 "intra- community" 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 cnter-community pairs of vectors, prove an upper bound on the pre PCA distance and 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 yr' for any (t, i') pair.
| x/
B.3 Pre PCA distances
Lemma B.2. Let ys and yr be two vectors (datapoints) of Y with ground truth communi- ties Vj and Vy respectively. i = j' then we have 1ly ye 2 / /2do3 12a dolog with probability 1 - O(n otherwise if j + j' then we have 1lys yrll 1
v d(o + 0z)) + ||e 112 + 12ay dlog logn n with probability (n=
Proof. We know that for any (i, pair l1y. yr = ||,, xz Using this fact we prove the bounds on the datapoints of X.
First consider the case when æ; and a. belong the same community. Then | xy 1|2
Et (2.. Here for each é we define un (m:); (mx)): = (c))e+ + (et): - (c, e-
(cv); = (et). - (ex)e. Then E [uo]] E((((e)))) ((((er)) = Var((e))) + Var((cz)))
We define oř.; Var ((e4)) (to the more familiar row major representation). Recall that both e and e,' are sampled from D(j) and o² is the average of variance of the coordinates of the distribution Σd= o7, + o = 2do Now recall that the random variable w, is the range [-2, 2] for any f. Then applying Hoeffding bound on this setup we get
D(), i.c., E Ee wil
d
Pr
: < 200 12a n S n -3
14

---

Thus, if 2y and az belong to the same community then with probability - we have ||= myll 2 v 2do3 12x² Vdlog..
Similarly, if x4 and æy belong to different communities V, and Vy,, we have the random variable we (#4),= - (xz), with mean (cz), - (cyr), (due the difference in the centers and variance
oi, + o.. where we define Ct2 = (c)))- Then E [wm] = of + + + (ces c.. and
E
Σ Wi
Σ E=1
oi + oz. + (ces = d(o) + + + ||q c
Applying Hoeffding bound we get
Pr Σ w ž d(o) +le, - cy. c2, + 12a 12avdlogn $ nn
Thus if x, and x. belong to different communities then with probability - n -3 we have || ævll S V doo +oz) + cg. 12 12ov
Now, move into the analysis of post-PCA distances, which is the more technical part of the proof.
B.4 Post PCA distance
High-level idea. The idea behind the proof is simple.
In our setup, X = [ is the ground truth matrix, such that if the i-th column of X belongs to V,, then the i-th column of is Cj. Thus, X rank and thus | (cj - 'y'il || - cy This implies Y has rank & and ||Pp-1(c (cj cy)ll = ||q cyll- The crux of the proof is to show that pk-1 can be well approximated with P even when Y and Y differ significantly (due the y
noise).
To achieve this result we use tools from spectral analysis of random matrices, i.c. 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 focus closely related symmetric matrix through the following symmetrization trick, which is essential to the proof. We define the matrix & as
0
Y
Z Yr 0 This is d d + symmetric matrix. We show that pk-1 can be
analyzed through pk-1 and then approximate the second projection operator using pk-1 borrowing tools from classical random matrix theory. This gives us preliminary post PCA distance bounds expressed using ||Y Y|I.
2. Then obtaining the exact bounds of Theorem B. require bounds on the spectral norm of Y-Y Y. There exists a rich literature on spectral norm of random symmetric matrices with independent entries, but Y - 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 Y are not independent either. To this end, we first obtain the said properties for [[X] borrowing tools from [u188 on our symmetrization trick, and then accommodate for the effect of centering using results from 44 to complete our proof.
We now describe the symmetrization trick and its implications in detail.
B.4.1 A comparable symmetric case
We start by recalling the symmetric matrix corresponding to Y. yr Y]
As per our notations
0
we denote = [ and then we have = YT
Furthermore we have Ez Z Z.
15

---

Then the eigenvectors of Z and singular vectors of Y (and similarly Z and Y) are related as follows.
Fact B.3. Let the left and right singular vectors of Y be l, S L - d and fr. 1 < L S respectively,
[ with eigenvalue d₃ 8t and v2
4 Pt.
Then the eigenvectors of Z are
with eigenvalue
V2 fr]
d 8t where 1 < 1 S min(d, n), The same follows for Y and Z.
Here we also formally define P/ for symmetric matrices M as 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 PX as the matrix whose rows are the top k' singular vectors of M.
However, when we discuss a symmetric matrix M', Pi 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 py and Pz.
v 0
Fact B.5. Let be the n dimensional zero vector. Furthermore let v/0" == Then for any d-dimensional vector e we have |PP a|| [| (2
for any vector v.
This result allows us to work with the symmetric matrices Z and 2 instead of Y. Now we obtain the results needed to approximate Pz with PK
Difference in spectral projections of and Z: Here we use the Kavis-Kahan Theorem [DK70 along with result by Cape [CTPI9] obtain upper bound between the norm difference of the leading cigenspaces of Z and Z under some appropriate orthonormal rotation that we shall use obtain our results. The main reason behind using these tools is that the SVD projection matrix due to Z is well behaved.
Theorem: (DK70). Let D and D be p x p symmetric matrices, with ; Ap and Xi,..., Xp respectively, Define EnD Đ- D and ox D - S <. Let U (u1..... Uy] and [ũι ..,, úzف are matrices Boxk where un and ús are eigenvectors of D and D w.r. to the i-th top eigenvalue. Then
Theorem B.6
eigenvalues -
sin (U.
2
Theorem B.7 (Perturbation under Procrustes Transformation: CTTP1)). Let U and U be two p x k matrices such that the columns of U (and similarly Ú') comprise of K many unit vectors that are mutually orthogonal.
Then there exists k k orthonormal matrix We such that
sin θ (U.O) < 1U -Wwlll s v2
/2|(sin sin + (U,
Combining them we get the following result.
Theorem B.8. Given the matrices Y and Y and Z and Z defined as described above, there exists an orthonormal matrix Wz such that
|( - - (TW2)
2 Ez 8x (Y)
<
This in turn implies
E2l (Y)
Wz P/
Next, we obtain result the projection of random vector A dimensional subspace.
16

---

B.4.2 Random Projection
Now, we derive a strong bound for || ell where E IE is coordinate wise independent random vector with mean o and M is any d x n non-negative matrix. We essentially show that for any || = (vk) even though e = 92( (dd) with high probability. Here an important condition to be satisfied is that M and e. are independent.
Then the projection matrix PM is set of k-orthonormal unit vectors Pt, 1 S S k. Then the length of projected vector [|P]] ell can be written down as
||
Σ ((p)) t=1
Here one can do an entry-wise analysis of the terms ((p))"e)* but that forces bound of the form
that || Pi ell < vī(la + (16log(nk) with probability 1 (( Instead, we recall a result from the Vu [VWI5].
Lemma B.9 ([WW15). There are constants Co Ct such that the following happens. Let e be random vector in Rdd such that its coordinates are independent random variables with O mean and variance o², Assume furthermore that the coordinates are bounded by o in their absolute value. Let H be subspace of dimension & and let 11 (e) be the length of the orthogonal projection of e onto H. Then for any n we have
Pr (Iz(e)) 2
(I)((())20VB ovT Clavlogn) In
Now, let us consider the case where H is the subspace covered by the top k many orthonormal
eigenvectors of M, denoted as Pe, 1 S t k. Then the projection of onto H can be written as
Ex (Pe, e)Pt. Then we have (1)=(e))² Et= (Pr, e)² Σ ((P.)"e) "eee)")) e)" (e)(2) Summarizing, we get the following result with respect to the matrix Z.
This is exactly
Corollary B.10. Let Phz be as defined above. Let e be a d-dimensional random vector with each entry having zero mean and variance at most o². Then with probability 1 - n we have,
| (e)]l S <ovk Cr a Vlogn
We are now in position to obtain our preliminary pots PCA distance bounds when the projection dimension is
B.4.3 Preliminary post PCA bounds
Preliminary intra-community bounds: We start by obtaining the post PCA distance | (y: yr'll where both ya and yı belong to the same community Vj-
Lemma B.11. Let yi and yı be two columns of the data matrix Y belonging the same community Vz. Then for some constants C₁ we have
IP (y: -vv)l < 2 2 7|1 1 -vrll +2v2 oov + vlonn
(5)
with probability 1 33.
Proof. Initially we have || (yt yr)ll 2 (yi 0" yy (0))]. Here use the facts
that the spectral projection operators due to Z and Z are close up some orthonormal rotation and that Z and yı yı' are independent. Furthermore yi yr Cj ee -ex Cj' er tex = = e,', where ex is the centering vector which is zero
random vector.
Then we have for any k- dimensional orthonormal matrix W,
| Z (yE 0n - ye 10") < [1(p WPP (yx |0") + ||W (y:10" p y ||
< |
WP
|| || 10-10"1| + |W papppkk-aaa
2 (eg/00 e. Or)]
2
|
Wp ||9//0" 11-10"1| + | P ee + | | 10
17

---

From Theorem B.8 we have that for choice of W ||2--1 -WP2-1
212-21 82-1(2)
2112-2
Next, we can analyze | [WP2 - | + W P er 0*| as Z and the vectors are independent of each other. Then applying Corollary B. 10 with probability 1 (n 3) we have |WP2 | |e ||W -
e0r10"|| I 20 2o 1 + 201 log This completes the proof.
Preliminary inter-community bounds. Now, we move to the inter-community results. In this part
P
plays an important role. This is because as per our discussion || P -1 '(; - cy)ll = [|g - cj ||-
This implies
(P/10" Y, |0
|c cy
(6)
Using this result then prove the following inter-community post PCA bound.
Lemma B.12. Let Yı, Ye be two columns of the data matrix Y so that E Vj and E Vjs, where
j + J. Then for the constant C1 we have
[|P - v2
(1g (18-c-11-2 syll -15-ccll-2(o))) (oVT O aa. Vlogn)
2 /|| 11
y/
6k-1(Y)
with probability O(n
Proof. As before we have || (y: - yr = v P (yx - -9-10-))11 Then we proceed with a basic decomposition. We have for any k: dimensional matrix W.
1 yı [I
2 2| p (c/10" Cj. |0")|
W P - (e:10" - e. |0 1( WP (B: y 10")
Now, we have I p (cy 0r cy (0*) = || (q - -g)l ||| ||, -crll
Next from Lemma B.11 we have | || (eal00
- (
- |0))) s (ov + Ci Civlogn with proba-
bility
(n 3)
with Finally from Lemma B.11 11 we know can upper bound [1(22-1 W WP WPp-l)) (vr yy y='10")]
2 Z||
1/4 yel |l. which completes the proof.
4x (Y)
At this point, we have obtained the pairwise post-PCA intra-community and inter-community distance bounds in terms of lly: 3 ||, 2 211, k, a and 6x)1 Here (Y) is the spectral gap of Y and we already have bounds on |/ı: - ye ||. Next, we obtain bounds on || Z|| and then put together the results obtained so far to prove Theorem B.1
B.4.4 Spectral norm of the square marrix
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 (ull8). Let E be a n x 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 Co such that
Pr
[]] 2 Coavn] -3
where x² C1
log
However, since the entries of Y are not independent, the same follows with Ez. To bypass this issue
X
we define the matrix B XT 0
and then B E XT
Furthermore recall that Ea M E[M] Then have the following results.
18

---

1. | EE || is the largest eigenvalue of Ez, which is same as the largest singular value of Ey, that we denote as $1 (E
2. |B is same the largest singular value of Ex, that we denote as si (Ex).
Furthermore we have from Theorem B.13 that |Bll S Cn with probability 1 O(n 9). Finally we connect 81 (Ey) with $1 [E To do so, note that Ey the centered matrix of Ex. This follows from the fact that Ey Y Y and Ex X - X. Then Hanoine 14]
the following result by
Theorem B.14 (4Ha)14)) Let M be rank m matrix and M be the matrix obtained upon centering, with singular values (in descending order) 8 $1...., 8m and 31,.... m respectively, Then for any 1 S i m we have s; 2 s/ 2 81+1.
Using this result get
Ezll = #1 S (Ex) & EBll
O (Ex)T
Ex
Now, we bound || | i.c.
This is a (d+n) x (d+n) random symmetric matrix
with zero mean and maximum variance a². Then applying Theorem B.13 we get the following bound. Lemma B.15. Recall that we define = Coovd+ n. Then in the setting of Lemma B.11 we have
I Z|I N with probability 1 O(n
Against this backdrop summarize our bounds prove Theorem B.1
B.5
Proof of Theorem B.1
From Lemma B.2 we have the lower bound on the intra-com cotraccommuntyy 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. is easy to see that (i.i') belong the same community Vj then with
probability - On 3), 1/
yıll - V 2do + 12avdlogg
Substituting this and the bound on Z Z|| Lemma B.1l we have with probability O(n -3)
N. v 2200 + 12xx logn
P - s 2/2 oVT + C Vlogn-
Similarly for the inter-community with i V,, E V2 from Lemma B.12 we have
N 11
c 1 + d(o} + o3.) + 12avdlog)
||P 1Ip--1(1- (y:-v+)]1 2 V2 [|q] cpll - (ov C a Vlogn]
(y:
8x-1
Finally, using the bounds of Lemma B.2 and applying a union bound on the total n² pairs of datapoints completes the proof of the theorem.
C Spatially unique centers and proof for the outlier detection theorem
The primary quantity that is hard to interpret in a dataset with an underlying community structure is 62-1(Y). (Y). Here make some observations. First note that 6x-1(Y') sx-1(Y) - sn (Y). Now, (Y) > (x) and sY) < Covd+n where the latter term comes from the fact that (Y) < Ey < ||Ex| < Covd+n n. This follows from simple application of Weyl's inequality and the effect of centering on eigenvalues. For simplicity, we consider the case when xx(X) 4d n. We will come back this and show that this assumption does make sense. Then, we have (Y) 2 0.66s,(X) (X). Next note that sx(X) 2 8y (E[ ||E||
This then implies that given the aforementioned conditions, have
(8) where E [[X] the center matrix, where each column is the center of the community the corresponding point belongs to.
6 2 0.25s, (E[X)
19

---

Similarly for any E V, and i' Vy, the inter-community compression ratio is upper- bounded as Bounds on the singular values of the center matrix for y-spatially unique centers Here, we make a connection between Sy. (B[])) and the notion of spatially unique centers.
Given a 1i x n2 matrix M, we define the minimum hyperplane distance, distm as
distm = min VESpan(M1,)
min
MM, vll
where M, represents the j-th column of M and M-j denotes the set of all columns of M except the j-th one.Thal is, it denotes the minimum distance between a data point and the span of the rest the data points.
We have the following classic result of matrix theory.
Lemma C.1 (RV08)) For any ny x n2 matrix M, the smallest singular value Smin (M) ) is lower bounded by 702 distm-
Now, this result does not directly help us as E[ has multiple identical columns (it is after all a n rank matrix) and we only get lower bound of O. However, we can do a simple two-step analysis to get something nicer.
Consider the matrix Ö which contains columns that are each copy one of the centers of X. Then from the definition of 7-spatially unique centers, immediately have the following.
Fact C.2. If X comes from setup with 7-spatialyy unique centers then sy (Ò) 8min (C) 2 V
Next, let the size of the underlying communities in X. Then we know that E[C] has at least miny [V] many copies of Ò in it (along with other columns corresponding to the larger communities). That means that the singular values in E[X] is least /min, [Vyl times the singular values in Ć. This gives us the following result.
Lemma C.3. Let X be generated from 7-spaiallly unique centers and let the minimum size of the underlying communities be (2m/k)) Furthermore, assume si(X) | ||. Then we get
5, 1)) 2 C-yy/ for some constant C.
Proof. This simply comes from putting the bounds on Ô and multiplying them with / min, VV and then connecting it with Equation g
Now, go back the assumption of (X) > 4Cood n, consider that 22(d) (this is where will work from hereon), then the assumption holds as long as 7 2 ok. Now, once we have this result, can then obtain main Theorem C.4 in the setting of Spatially unique centers.
Theorem C.4 (Relative compression with spatially unique centers). Let X be d x dataset k many 7-spatially unique centers where the size of the smallest community is ((n/ m/)k. Then there is a constant Cj such that for all hntra-community pairs in Vj, the compression ratio is upper-bounded as
,vvd
Ax,x-1(, 2
Ci Ci(o 20.0, .kva kvdd
Ax
(00 + [ )z d2² + ||ej c
(10)
Ci ||: cyll 20 av a. a k.
with probability 1 O(1nn).
20

---

Proof. For simplicity of the statements we have made several assumptions, most of them to consider the harder setting (heavy noise). That is, ozd {mmaxy ||c cyll). Furthermore, we assume is sufficiently large so that o²d 2 100av log (this happens as long =o(d"/)). This implies that the pre-PCA intra and inter-community distances are 0(2ayvd) and θ (V03 + o3 respectively.
Next, in the intra-community compression ratio bound we have the term
2N V oodd + 12 2ovd+n n o3 12avdlogn
8:- 8Y)
0.257/n/k
Here recall that assume n s2(d) which implies 20 2o S Covnn for large enough Furthermore, 12av log is dominated by ofd. Combining we get
2x v + n. v o33 + 12ovdlogy Covno,val 8Coo, k Vd
0.25%vn/
0.25%
Similarly the bound
20 20 +n n.
||o cy c 112 220 + o3.)d + 12a 12a
5x 6x-1(8)
can be simplified 0
Combining these bounds directly gets us result.
Then, Theorem 2.5 is immediately implied, follows.
C.1 Proof of Theorem 2.5
We know that y 2 C (ax ov + a logn). Furthermore, we assume max;, ||q -clllll < v which is the heavy noise setting. The other case follows the same way. Let C > 100C. Furthermore, note that | cjll 27.
Then we have
20 oj. kvd < /k0
7
Similarly, we have
o0 + oz. k- Vd
0.0lo
Then, the denominator of the lower bound on the intra-community compression ratio is upper bounded by 0.02o//kd//4 and the denominator of the lower bound on the comerncom compression ratio lower bounded by ||c: ||g]ll 0.02ovTa//4 2 0.98a 0.98o 1/4
Then, the mntra-commmmit compression ratio is lower bounded by 10 and the inter- community compression ratio is upper bounded by 0.05 obtaining the separation described in the Theorem 2.5
C.2 Proofs for variance of compression ratios
Having discussed the compression ratio bounds in the context of y-spatially unique centers, continue with the theoretical support for our outlier detection method in the random-mixture-ouliee model. We recall the definition of this model for case of exposition.
21

---

Definition C.5 (Mixture model with outliers (revisited)), Let X be d x n dataset with the partition ( and distributions (DD)) 1=1 + with the following generation Vi.... V. a set of l centers method.
1. clean points: If E V,, 1.,15js 2; = = + where e, is sampled from D())
2. outliers: If V, then we sample p.. Pi,k E [0.5, 1]. Then Ex at, te, where Pi.i and e, is sampled from D(++1), 0i.j Ey
Let |V|= = no and n n. + ne. To keep the results simple, we make the average variance of each distribution DG) same, which is o'.
The concept of Algorithm| Tis simple. If each cluster has large number of points, then even there a large number of outliers generated from the nuut model, the outliers will have a lower variance compression than all the clean points.
First, let obtain lower bound the variance of the compression ratio of clean points under the conditions of Theorem 2.8 We know that any clean point has high iotra-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 large value.
For the sake of simplicity, we will define 7 2 /okddd Then if we can show that under the other settings of Theorem 2.8 there is separation in the variance of the compression ratios of the clean points and the outliers whenever 3 2 C" g/ooo we prove the theorem.
o'
Lemma C.6. Let there be ne clean points in the rundom-mixsure-oullicn setting where minj [V ((n/k) and 2 2B3/okd//4 Then the variance of all such points are lower bounded as C₃ Re-
1144
[Ba
a 3:0
with probability (11mn)
Proof. Consider any point 2; E Vj. Then the inter-compression ratio of æ; with any intra-community 0.25g' point is lower bounded by a +t d-14(())
0,2538' d1/4 with probability 1 O(1/n).
Then the average of the compression ratios for æ; is lower bounded 0.25o /oa
/oBo'/od'/4
On the other hand, probability 1 ((1/n) we have that for any inter-community point, the com- 20
pression ratio upper-bounded with (-- C C204d1/4) S
20y/d
Bko /0/4/02 S 2020/a 4/4
3.
Then, the variance of compression of is lower bounded by
n VV
d/44
( [0a'
2
C4
k
300
Now, we aim upper-bous bound the variance of compression for outliers. Here we want show that since the underlying signal in any outlier is apart from the signal of any other point, they generally have lower compression ratio with any other point, which then implies a lower variance of compression ratio.
First, we show that long as there are 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).
Lemma C.7 (Distance between signals of the outliers). Let there be n. many outliers in the dataset generated the mandom-mixture model where k: > log n. Let the set of outliers be V. Then, for with probability 1 (n), min miny ||u al logn'
22

---

Proof. Let [V| no. Then, for the underlying mixture-center any two points, denoted as Σ, an and Σ, a2.; we say they are e-far if min, [01. 02.j 2
Now, note that for any e-far mixture-centers, have ||u m 0.5ey.
Now, it is easy to see that the probability that there is a pair of mixed centers that is not c-far is n (c) Then, setting 1/ log n and applying k 2 log gives that even for ny = n/2, there all pairs of mixture centers are 1/ log n-far with probability
(1/n))
Then, show that in such 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 set of no many outliers so that
the underlying mixture-centers are pairwise /log n-far Then under the condition of Lemma C.6
have that the variance of compression for any outlier is upper bounded by with probability 1 - (1/nn).
(ACs log /
Proof. Consider any outlier uy E Vo. First, consider the compression ratio between us and any that is clean. Where Σ, ayCj + ey and v Cjr + e₁.
Next, remember that as every 0j 2 1/2k, we have max, oj S 0.5.
Then, from the definition of 7-spatially unique centers we have ajjj - (1 - ay )op 2 0.5||
Σ a, Cp 2 || Σ
Σ ag. - Cy.l 2 0.5g j75"
jf3
Then, following the analysis of Lemma
C.6 we can show that all such cases, the compression ratio
upper bounded by 4C2a /o' d-/4
B-
On the other hand, consider any two outliers. Then their compression ratios are upper bounded by 40, log no/ /a 2/44 (essentially replacing by 7/ log n in the center-distance calculation).
B.
Then, we can upper bound the variance of compression for an outlier as
1 ( [V] 4C₂ log /oo'dd )2 (n MVD( 4C20/o'd//4 n
4og |4 3.
B- )p)
)8) <
[applying A log
k
Proof of Theorem 2.8 Lemma C.6 shows that in the setting of Theorem
2.8 the variance of
compression ratios for clean point lower bounded by C4 n-|V/ 1/44 Ga'
n
k
Br
Next, Lemma C.8 shows that the variance of compression ratios for an outlier upper-bounded
4C' log nla/o 4/4 Both the aforementioned happen for all outlier and clean points with B.k
probability 1- O(1m).
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 is
C4 n |V
dd/4
(8o'
Bo'
))
[4C2 log nía (ogn(a"')aa// 2
n2
k
Bo'
B k
n
V
Ba'
Cslog not
>
[For some constant Cs]
1
n
0'3
Vd
0.5,8a
Cs log no o'3
0
[As IV| 2 0.5n]
2
Then, as long as 3 2 10C50/0 Docio//''Vlonnn this equation is satisfied.
23

---

D Projection with more principal components
Here show some results in the case of k' = k our bounds for k' + k comes from Theorem B.8. is the following spectral gap.
The main challenge in theoretically proving A key ingredient towards proving Theorem B.1
2 2 8 (Y)
(1z) (1 ) [//
-
In general we work with the natural assumption - (Y) >> |E However, in our model we have (Y) = [ Ezl)- This follows from Weyl's ' inequality, which states that if Z = Z + Ez and (k")-th singular value of B is O, then (k: + e)-th singular value of upper bounded by ExIl) for any <>0 0.
Thus (Y) Ezll) for any k' 2 k, and our previous results alone cannot prove relative compressibility.
Here bypass this issue to loose but non-trivial extent. First note that the ioter-community compression can only decrease if the the projection dimension increases. Thus we have that for any k' 2 k. Ax, (i, I Ax,
Theorem D.1. Let us consider the random vector model as in Theorem B. and any 0 < f < 1. Then we have that with probability - (11nn)
Let Let k' +
1. If (i, is an communcymyuntty pair, then DE xxxxxxiii (i, S 1x-1x((,,))
2. If (1, is an intra-community pair, then
Vleo cyll2 + d(o} + oz.) 12vdlogn
(1,))
VI (v - - + 40 n
for all but e pairs of points with probability 1 O(1mn).
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 phi A2 the projection operator due to the kj -th to b2-th top singular vectors Y.
Then for any vector we have [[TT) = (2)]l2 + ||P (u)ll2
Then are left with bounding |IP& (u)ll where y/ Ye that i E Vj, Vy. We aim to show that k'' & is small then this value is small as well.
We first represent Y with its SVD decomposition. le and r2 represent the f-th left singular vector and right singular vector of Y respectively. Then we have Y = Eien 8: ((Y)) where & = rank(Y). Then the projection of yı due the f-th principal component of X (le. se(Y)rr, i where Te, is the i-th entry of the ê-th right singular vector. Then we have
E Σ (r2))2 t=
S Sss(F),
Here recall that each re is a n-dimensional vector with unit norm, i.c. ||re|| 1. Then for any f < 1, the number of coordinates of re that are larger than f is less than 1/f2. Thus considering all the k & l S k
+ c, the total number of entries that are larger than f is less than c/ Then, for all but c/f² many points y: we have ||PP (yti) s (x .f c. Here we substitute
(Y) < | || < Coovd n with probability 1 - O(n 3)
This implies that with probability 1 - ((1/n) || k- (y1 - welll < 20oo nef for all but e/5² pairs of points. This concludes our proof.
24

---

It should be noted that this is a much looser bound as compared to our (k- 1)-PC compression metric, especially the paradigm where noise dominates the ground truth distances. As we discussed, the main reason that Theorem does following technical challenge.
does not directly work for k' > k - can be pinned down to the
D.0.1 Technical challenges in understanding PCA
The technical challenge is getting a better upper- upper-bound bound on [|(2-- - -P than P 1P2--1
P -|eel] for random vector e. In fact, || (1 P - eell equals (P -) -|llllell only if e/lleel is a unit vector along which (P2-) be the case for most noise e vectors, due to the inherent randomness them. better analysis of this term will allow us to extend the result of Theorem B. k' = k 1, which is what we observe in reality. For real datasets, the compression factor does not change much the PCA dimension changed by a small value. Furthermore, tighter understanding of || [[(P)- enable to 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.c. SBM (stochastic block model). Generalizing these results to the random vector mixture model is an outstanding open question.
P2-11) realizes its spectral norm, which is unlikely to
P will also
E
Experiments
E.1 Summary of datasets
First, we present summary of the datasets.
#
# of genes
Dataset
of clusters
cells
(features)
Koh
531
48,981
Kumar
3
246
45,159
Simkumar4easy
500
43,606
Sinkumar4hard
499
43,638
SimkumarShard
499
43,601
Trapnell
222
41,111
Zheng4eq
3,994
15,568
Zheng4uneq
6,498
16.443
Zheng8eq
3,994
15,716
Table 4: Summary of data
E.2
Community-wise average compression ratios
In Section 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 higher than the inter-community compression ratio for all datasets.
E.3
NMI and purity index improvement for PCA-dim=k:
Now, we continue with providing more experimental results. First, we note down the NMI improve- ment when 5% and 10% of the points are removed the setting of PCA dimension= k 1.
Next, we add the initial purity scores when running PCA( dimension=k - 1-)--1)-eeeee means on the datasets in Table
Then the improvement in purity index due to 5% and 10% points removal are recorded in Figures 6
25

---

VMI Improveman: from Outlier Removal (dim k- 1,5)
Variance of Compression
0.42
LOF
NMI improvement
0.100
PCA +
KNN
PCA + KNN
0150
Isolation Forest
0.23
Isolation Forest
ECOD
0.00
PCA + ECCD
-0.050
Koh Kumar sk4e
sk4h
sk8h
Trap
Zh4e
Znáu
Zhße
Figure 3: NMI improvement via removing 5% points
Improvement Outlier Removal 10%)
Variance of Compression
LOF
0.30
PCA + LOF
NMI Improverr
0.66
KNN
i
Isolation
PCA Isolation Forest
0.30
ECOD
PCA ECOD
-0.12
-0.20
6oh Kumar sk4e sk4h
sk8h
Trap
Zh4e Zh4u ZnBe
Figure 4: NMI improvement via removing 10% points
Purity imprvemenn from Outilar Removal (dim k k-2,5 5%)
0.12
Variance of Compression
LOF
Purity Improvement
PCA + LÜF
0.8
KNN
0.88
PCA KNN
Forest
PCA + Isolation Forest
ECOD
PCA ECOD
0.00
Kch Kumar sk4e
sk4h
sköh
Trap
Zh4e
Zh4u Zhße
Figure 5: Purity score improvement via 5% outlier removal
Purity Improvemen: from Outler Removal (dim k 1, 10%
0.15
Variance of Compression
LOF
Purity Improvement
PCA + LOF
KNN
0.05
PCA KNN
Isolation Forest
PCA Isolation Forest
ECOD
-0.05
PCA ECOD
-0.10
Kch Kumar sk4e sk4h sköh
Trap
Zh4e
Zh4u
Zh8e
Figure 6: Purity score improvement via 10% outlier removal
26

---

Community wise average compression ratio
Koh (Inter)
2.417
2.530
2.714
2.523
2.649
2.948
2.352
2.696
2.018
Koh (Intra)
7.678
9.829
6.966
6.041
6.757
8.424
6.686
7.382
7,463
Kumar (Inter)
2.107
2.105
1.696
Kumar (Intra)
15.969
13.577
14.889
Simkumar4easy (Inter)
4.534
3.724
3.200
2.850
Simkumar4easy (Intra)
15.673
17.083
15.554
14.924
Simkumar4hard (Inter)
5.984
5.653
4.960
4.472
Simkumar4hard (Intra)
15.173
16.722
14.500
13,807
SimkumarShard (Inter)
4.425
4.668
4.397
5.233
4.390
4.004
3,998
3.681
SimkumarShard (Intra)
9.177
10.571
8.785
8.639
9.390
9.526
8.699
10.172
Trapnell (Inter)
4.491
7,401
7.228
Trapnell (Intra)
9.202
10.248
10.122
Zheng4eq (Inter)
2.117
1.762
2.828
2.889
Zheng4eq (Intra)
6.135
6,250
7.947
6.223
4ueng (Inter)
2.059
1.753
2.870
2.176
Zheng4uneq (Intra)
5.839
6.351
7.335
5.514
Zheng8eq (Inter)
1.981
2.922
1.655
1.936
2.567
2.594
2.802
2.726
Zheng8eq (Intra)
4.306
4.533
4.540
4.997
4.254
5.598
5.244
4.300
Table 5: Community-wee wise Inter and norra-Comuunity Compression Ratios
Dataset
Purity of PCA
k-means
Koh
0.895
Kumar
0.983
Simkumar4easy
0.918
Simkumar4hard
0.563
SimkumarShard
0.667
Trapnell
0.604
Zheng4eq
0.715
Zheng4uneq
0.873
Zheng8eq
0.568
Table 6: Purity index before data removal (PCA dim = k 1)
E,4 Different PCA dimension choice
Finally, we show that our experiments on real-world data, both for average compression as well as clustering accuracy improvement through outlier detection, fairly stable to change in the PCA dimension. The average compression ratios can found in Table The NMI and purity index baselines can be found in Tables 8 a respectively.
Avg. intercluster compression
Avg. intracluster compression
Dataset
Koh
2.246
4.484
Kumar
1.742
5.576
Simkumar4easy
3.007
6.496
Simkumar4hard
4.161
6,461
SimkumarShard
3.537
4.948
Trapnell
3.259
4.204
Zheng4eq
1.969
4.246
Zheng4uneq
1.893
4.081
Zheng8ey
2.9
3.491
Table 7: Relative compression on RNA-seq datasets when PCA dimension 21:
27

---

Dataset
NMI of PCA k-means
Dataset
Purity of PCA k-means
Koh
0.861
Koh
0.898
Kumar
0.924
Kumar
0.984
Simkumar4easy
0.744
Simkumardeasy
0.910
Siakumar-harr
0.235
Simkumar-hard
0.561
Simkumar8hard
0.440
SimkumarShard
0.658
Trapnell
0.293
Trapnell
0.608
Zheng4eq
0.710
Zheng4eg
0.720
Zheng4uneq
0.724
Zheng4uneq
0.878
Zheng8eq
0.560
Zheng8eg
0.574
Table 8: NMI before data removal (PCA dim
Table 9: Purity score before data removal (PCA dim 2k)
2k:)
NMI Improvemen: from Outlier Removal (dim 28, 10%)
0.15
Variance of Compression
LOF
NMI Improvement
0.19
PCA + LOF
KNN
PCA KNN
Isolation Forest
0.05
PCA + Isolation Forest
0.10
ECOD
-0.15
PCA ECOD
Kch Kumar sk4e
sk4h
skôh
Trap
Zh4e Zh4u Zhße
Figure 7: NMI improvement via removing 10% points when PCA dimension is 2k
For brevity, we show the improvement in NMI and purity index for 10% point removal in Figures 7 a respectivel...
one can observe, our method continues be the most consistent, being the best method in most datasets. Indeed, in this case our performance is even comparatively better than the case of PCA-dimension=k
F Future directions
In this paper, we have quantified PCA's denoising effect in high dimensional noisy data with underly- ing community structure 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 more tight bound on the compression ratio seems an exciting and hard direction.
Purity Improvement from Outlier Removal (dim 2k, 10%)
0.20
Variance of Compression
LOF
Purity Improvement
PCA + LÜK
0.0
KNN
PCA KNN
0.65
Isolation Forest
PCA + Isolation Forest
ECOD
-0.55
PCA ECOD
-410
Kch Kumar sk4e
sk4h
sk8h
Trap
Zh4e
Zh4u Zhße
Figure 8: Purity score improvement via removing 10% points when PCA dimension is 2k
28

---

ii) Using compression ratio as metric for clustering algorithms also seems an interesting direction, especially for single-cell-RNA- datasets.
29

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide a novel quantification PCA's denoising effect in high dimen- sional data with heavy noise. Then, use this quantification develop outlier detection method in this setting. We provide comprehensive theoretical, simulation, and real-world experiment results in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in the last paragraph of the main paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer: [Yes]
Justification:
We provide the proof of our theorems in the Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We describe experiments clearly in Section 4 and provide the full source code used to generate the results in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
31

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Cooee//mddeeSbmimiia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all experimental details within Section of the paper and additional results within Appendix E for different experimental settings.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide error bars for all the applicable experiments, mainly in Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
32

---

The method for calculating the error bars should be explained (closed form formula, call 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.
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 96% CI, if the hypothesis of Normality 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 out of range (e.g. negative еттоr 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe the computational environment and running time used to generate the results in the first paragraph of Section
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 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
Answer: [Yes]
Justification:
We have read and understood the guidelines
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal 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 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
33

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the
11. Safeguards
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)?
Question:
Answer: [NA]
Justification:
We do not any immediate risk of misuse of our work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 used and, possible, include a URL.
The name 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 package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
34

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Ys]
Justification:
We provide codes in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "yqqhXcj35g", "reviewer": "Reviewer_51iT", "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.", "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.\n2. 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? \n3. 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? \n\nJiashun 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\n\nAlso see my questions in the weakness section.", "limitations": "Yes, limitations are discussed.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper theoretically shows that for clustered data that are well separated and each cluster centroid is situated in a subspace, not representable by the span of centroids, the compression within clusters is greater than compressions between clusters, implying the formation of tight clusters in the reduced low-dimensional representation.", "weaknesses": "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.\n\n2. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. Please find our responses below.\n\n**Comments regarding weaknesses:**\n\n**Regarding unrealistic conditions of centers:**\nThe reviewer comments that the assumption of centers being nearly orthonormal is unrealistic for the case of n>>d (where n is the number of data points and d is the dimension). This is **an incorrect evaluation of our theoretical contribution** in our understanding. First, we point out that our assumption can be interpreted as each center (there are $k$ centers in total)  being not *a linear combination of others*. This assumption is *much weaker* than nearly orthonormal. Our assumption covers many natural benchmark models, such as the stochastic block model. Secondly, even the realizability of this weaker condition has no connection with the comparative values of n and d. \n\n\n**Outlier detection in PCA:** \nAs the reviewer pointed out, PCA is not robust to outliers in  *all* scenarios. In this paper, we mainly focus on *high-dimensional noisy data*, which we present in the random mixture vector model with subGaussian noise. First, we observe the compression ratio phenomenon of PCA in simulation and *all* the datasets that we consider. Then, we use this phenomenon to detect outliers in this model. Furthermore, The overall performance of our outlier detection algorithm on a large set of real-world datasets is a strong support of its efficacy. \n\n\n**Answer to questions:**\n\nQ1) Regarding “explained variance”: In this paper, the compression ratio is defined on k-dimensional PCA projection and the amount of information retained is dependent on factors such as k and the variance of the noise in each community. Among our datasets, the top k singular values range from 3%-10% of the sum of the singular values, depending on the noise level of the datasets. There is a very weak correlation between this value and compressibility phenomena.\n\nQ2) The vanilla PCA algorithm works for **any** rectangular matrices, and as such, we do not need to use a different method for d>>n and n>>d. \n\nQ3) The goal of the paper is to analyze the “compressibility” of PCA itself, and as such, we do not focus on other PCA variants. It is an interesting future direction to see if similar compressibility phenomena are observed in other variants of PCA, and we thank the reviewer for their suggestion.\n*Regarding the PCA based clustering method:* Please note that we do not propose a clustering algorithm in this paper. Rather, we use the compression ratio metric to observe the denoising effect of PCA in noisy high-dimensional data with underlying community structure. Next, we use this metric to design an *outlier detection* algorithm. Therefore, comparisons with PCA-based clustering methods are not relevant to the paper.\n\n\n\n\n------\n\nWe hope this answers the reviewer's questions, and we will happily answer any other queries they have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BCpAgCUumI", "reviewer": "Reviewer_1iTr", "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.", "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? \n-", "limitations": "See questions and weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper studies a problem of good interest and provides a clean, well-motivated solution.\n- The theoretical results are interesting", "weaknesses": "- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments. Please find our answers below. \n\n**Regarding the theoretical assumptions:**\nOur theoretical setting is a generalization of several popular unsupervised models, such as the Gaussian mixture models and the stochastic block model. The noise distribution we consider is SubGaussian with very high variance. Such distributions capture noise observed in many real-world scenarios, such as datasets with bounded entries (as all bounded variables are subGaussian). \n\nNext, we note that our outlier detection algorithm *does not* need knowledge of the number of outliers. We prove that if the data has outliers in the random mixture model setting, these outliers will have the lowest variance of compression. \n\n\n**Regarding the weaker performance in figure 1(b):** \nWe start by noting an observation from the outlier detection survey paper we referenced (HHH+22) that the success of an outlier detection algorithm depends on how closely the assumption behind the algorithm matches that of the dataset. In our paper, we theoretically studied our outlier detection algorithm in the case where outliers are generated as random mixtures of community centers further perturbed by noise, which is essentially the same as a random mixture of the points in the communities. \n\nFigure 1(b) is for a *different* kind of outliers. Here, outlier points are generated by adding a “higher variance noise” to the corresponding community center compared to normal points for that community. Note that this is an outlier model different from the one we theoretically study. In fact, outlier detection methods like LOF are known to have a very good performance in such settings (HHH+22). We wanted to showcase that our method can be competitive even when the outlier model differs from our theoretical model. We hope this will further increase confidence in our outlier detection method.\n\n\n\n------\n\nWe hope this answers the reviewer's questions, and we will be happy to answer any other queries they have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ssLUXRohiu", "reviewer": "Reviewer_mA6h", "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.", "questions": "1. In Figure 1, why is the variance of compression achieving moderate to low ranks? \n2. The simulated outliers seem to come from a convex combination of existing clusters — have the authors considered more general outlier cases?\n3. I would encourage the authors to provide more simulation results with higher dimensionality (right now it uses d=1,000 < n=3,000)?\n4. 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?\n5. 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. \n6. 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": "Detailed in questions.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors provided a detailed statistical setup for the problem and provided theoretical guarantees of components of the algorithm. \n2. The idea is quite simple and elegant\n3. The simulation shows that with moderate noise, the proposed method achieves good outlier removal methods.", "weaknesses": "1. More robustness/sensitivity analysis would be needed to help understand how widely applicable this simple ratio is. \n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments. Please find our response below. \n\n\n**Motivation behind real-world application:**\nWe thank the reviewer for their input. First, we observe that such mixture model approaches are predominantly used in data with access to bulk-RNA seq data, which can be less complex than single-cell RNA seq data [1,2].\n\nMore importantly, we note that the highly cited work [3]  laid down a standard pipeline for single-cell RNA seq data. Here, preprocessing is followed by clustering, and then the clustering is used to find differentially expressed genes (DEG) in the data (i.e., features that have predominantly high values in one cluster compared to other clusters). In such cases, a better separation of the underlying data can be beneficial in better DEG detection. As our outlier removal improves the performance of clustering algorithms such as PCA+K-Means, we hope it may be of interest and use to bioinformaticians. \n\n**Answer to questions**\n\n**Weaker performance in Figure (1):**\nWe start by noting an observation from the outlier detection survey paper we referenced (HHH+22) that the success of an outlier detection algorithm depends on how closely the assumption behind the algorithm matches that of the dataset. In our paper, we theoretically studied our outlier detection algorithm in the case where outliers are generated as random mixtures of community centers further perturbed by noise, which is essentially the same as random mixtures of the points in the communities. \n\nFigure 1(b) is for a *different* kind of outliers. Here, outlier points are generated by adding a “higher variance noise” to the corresponding community center compared to normal points for that community. Note that this is an outlier model different from the one we theoretically study. In fact, outlier detection methods like LOF are known to have a very good performance in such settings (HHH+22). We wanted to showcase that our method can be competitive even when the outlier model differs from our theoretical model. We hope this will further increase confidence in our outlier detection method.\n\n**Types of outliers:** As we have noted above, apart from the outlier model where outliers are convex combinations of points in the communities (which we study theoretically), we also provide results for the case where outliers are points with higher variance noise (which we present in Figure 1(b)). Apart from that, we also test our method on a large set of single-cell data. \n\n**Simulations for d>n:**  Following the recommendation by the reviewer, we also ran experiments with d>n by setting d=4000 and n=2000. We obtained identical performance as the ones shown in the paper. In fact, for the higher noise case, our outlier detection performance was comparatively even better than the other methods. We shall add this result to the paper. \n\n**Choice of PCA-projection dimension:** We did not consider this question in this paper. This is indeed an important question. In our experience, simple techniques such as elbow plots on the eigenvalue of the covariance matrix seem to be a good technique for obtaining a good choice. Additionally, there exists a large body of work on choosing the correct PCA dimension for noisy high-dimensional data. \n\n**Run-time complexity:** Indeed, calculation of all O(n^2) distances is necessary for obtaining the variance, bringing the time complexity to O(n^2*d).  \nFor the datasets we consider, our algorithm runs under 3 minutes, with it running under 5 seconds for the smaller datasets (less than 1000 points). We also want to point out that the distance calculations are highly parallelizable. \n\nFurthermore, theoretically we can improve this runtime significantly in our model. For each point, we may sub-sample a few points O(sqrt(n) log n) and then calculate the compression ratio with these points to obtain the variance of compression. This would reduce the run-time to only consider n^{1.5} log n distances. Empirical verification of such speedups is a future direction. \n\n\n[1] Song, Liyang, et al. \"Mixed model-based deconvolution of cell-state abundances (MeDuSA) along a one-dimensional trajectory.\" Nature Computational Science 3.7 (2023): 630-643\n\n[2] Chu, Tinyi, et al. \"Cell type and gene expression deconvolution with BayesPrism enables Bayesian integrative analysis across bulk and single-cell RNA sequencing in oncology.\" Nature Cancer 3.4 (2022): 505-517\n\n[3] Heumos, Lukas, et al. \"Best practices for single-cell analysis across modalities.\" Nature Reviews Genetics 24.8 (2023): 550-572.\n\n\n-----\n\nWe hope this answers the reviewer's questions, and we will be happy to answer any other queries they have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "osjB5iyxh1", "reviewer": "Reviewer_QWbP", "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.", "questions": "Can more metric comparison be included such ARI?\nTable 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": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. the paper studies an important question that how to characterize the improvement of dimension reduction via PCA in denoising and clustering.\n2. the proof part is solid and sound\n3. the experiment part is rich and convincing, validating the theoretical analysis part", "weaknesses": "The paper only conduct experiments on single-cell RNA-seq, which is not convincing. Results on more datasets are expected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments. Please find our response below. \n\n**Regarding only using single-cell data:** \n\nWe first note that single-cell is indeed a very important data-type with various applications in immunology, neuroscience, and others. The Science Journal placed it as the breakthrough of the year in 2017. Also, many machine learning papers use single-cell data primarily for experiments, including recent NeurIPS papers [1,2] \n\nAdditionally, we have tested that the compression ratio phenomenon of PCA is widely present in **high dimensional noisy data**. For example, we ran our experiments on a certain AFLP dataset [1]. Furthermore, this phenomenon can also be observed in popular image datasets such as MNIST and F-MNIST if they are artificially corrupted with high variance noise. Although we observed the compression ratio gap on these datasets, they do not have natural outliers. Hence, we did not include the compressibility results due to the space constraints of NeurIPS papers. \n\nBy contrast, single-cell data is a very good fit for high-dimensional noisy data with natural outliers. Some erroneous cells are the results of mixtures of different cell types or cells disproportionately affected by noise, which makes this datatype an ideal candidate for our outlier detection method. \n\nOverall, we are also interested in testing more high-dimensional noisy datasets with natural outliers. If the reviewer has such datasets in mind, please let us know, and we will be happy to test more.\n\n**Other clustering metric:**\nWe can surely show improvements in other clustering metrics, such as the ARI. Following the reviewer’s recommendation, we ran these experiments and observed that our method provides the second-best rank for ARI. Here, we want to note that ARI seems not to give an accurate picture of the clustering outcome if the clusters have varied sizes, and indeed, all of the outlier detection methods had weaker improvements in the ARI metric compared to both NMI and purity. \n\nAs a summarizing step, we calculated the ranks across different metrics (NMI, ARI, and purity), and our method (variance of compression) had the best overall rank by a significant margin. For example, for dimension k-1, we had a rank of 2.8, whereas the next best rank was 3.7.\n \nOn a separate note, we will fix the heading of the table as pointed out by the reviewer (yes, the right column is for 10% purity). \n\n[1] Gong, Jing, et al. \"xTrimoGene: an efficient and scalable representation learner for single-cell RNA-seq data.\" NeurIPS2023.\n\n[2] Palma, Alessandro, et al. \"Modelling single-cell RNA-seq trajectories on a flat statistical manifold.\" NeurIPS 2023 AI for Science Workshop. 2023.\n\n------\n\nWe hope this answers the reviewer's questions, and we will be happy to answer any other queries they have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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).
Decision: Accept (poster)