Partition First, Embed Later: Laplacian-Based Feature Partitioning for Refined Embedding and Visualization of High-Dimensional Data
Authors: Erez Peterfreund
Ofir Lindenbaum
Yuval Kluger
Boris Landa
Venue: ICML 2025 oral (2025)
Keywords: data visualization
dimensionality reduction
manifold learning
data embedding
feature partitioning
Primary area: general_machine_learning->unsupervised_and_semisupervised_learning
TL;DR: We present a feature partitioning approach for embedding and visualizing multiple low-dimensional structures within high-dimensional data

Abstract: Embedding and visualization techniques are essential for analyzing high-dimensional data, but they often struggle with complex data governed by multiple latent variables, potentially distorting key structural characteristics. This paper considers scenarios where the observed features can be partitioned into mutually exclusive subsets, each capturing a different smooth substructure. In such cases, visualizing the data based on each feature partition can better characterize the underlying processes and structures in the data, leading to improved interpretability. To partition the features, we propose solving an optimization problem that promotes graph Laplacian-based smoothness in each partition, thereby prioritizing partitions with simpler geometric structures. Our approach generalizes traditional embedding and visualization techniques, allowing them to learn multiple embeddings simultaneously. We establish that if several independent or partially dependent manifolds are embedded in distinct feature subsets in high-dimensional space, then our framework can reliably identify the correct subsets with theoretical guarantees. Finally, we demonstrate the effectiveness of our approach in extracting multiple low-dimensional structures and partially independent processes from both simulated and real data.

Partition First, Embed Later: Laplacian-Based Feature Partitioning for Refined Embedding and Visualization of High-Dimensional Data
Erez Peterfreund
Ofir Lindenbaum 2 Yuval Kluger 134 Boris Landa 15
Abstract
ding it in a low-dimensional space, making it more suitable for visualization and downstream analysis. Such methods aim to reduce the dimensionality of a dataset while pre- serving its underlying structural characteristics. Specifically, given N observations with features, { C RD,, stan- dard techniques such as Laplacian Eigenmaps (Belkin & Niyogi, 2003), Diffusion Maps (Coifman & Lafon, 2006), t- distributed Stochastic Neighbor Embedding (tSNE) (Van der Maaten & Hinton, 2008), and UMAP (McInnes et al., 201 8), first construct an N x N similarity graph between the given data points using all D features. Then, they embed the N graph nodes in a low-dimensional space where certain structural characteristies of the graph are preserved.
Embedding and visualization techniques es- sential for analyzing high- high-dimensional data, but they often struggle with complex data governed by multiple latent variables, potentially distorting key structural characteristics. This paper consid- ers scenarios where the observed features can be partitioned into mutually exclusive subsets, each capturing a different smooth substructure. In such cases, visualizing the data based each feature partition can better characterize the underlying processes and structures in the data, leading to im- proved interpretability. To partition the features, we propose solving an optimization problem that promotes graph Laplacian- baaed smoothness in each partition, thereby prioritizing partitions with simpler geometric structures. Our approach gen- eralizes traditional embedding and visualization techniques, allowing them to learn multiple em- beddings simultaneously. We establish that if sev- cral independent or partially dependent manifolds are embedded in distinct feature subsets in high- dimensional space, then our framework can reli- ably identify the correct subsets with theoretical guarantees. Finally, we demonstrate the effec- tiveness of our approach in extracting multiple low-dimensional structures and partially inddpnn- dent processes from both simulated and real data.
However, when the data's underlying structure is highly complex, standard methods may struggle accurately cap- ture and embed it in low dimensions. In particular, we are motivated by settings where several different groups of features are governed by distinct latent variables, each representing unique low-dimensional substructure. If the number of unique latent variables is large, visualizing the data using all features with (SNE UMAP can severely distort the data's 's underlying structure and fail to disentan- gle distinct latent variables (Kohli et al., 2021; Chari & Pachter, 2023). For Laplacian Eigenmaps and Diffusion Maps, there significant redundancy in their representation that grows non-linearly with the number of underlying latent variables (Blau & Michaeli, 2017). This phenomenon is due to the eigenstructure of the graph Laplacian, where many eigenvectors dependent and represent overlapping direc- tions of variation. As a result, when the number of latent variables is large, the embedding dimension may need to substantially exceed it to fully capture the data's 's structure.
1. Introduction
Dimensionality reduction methods are crucial for extracting scientific insights from ligh-dimensional data by embed-
To address this challenge, we propose to partition first, em- bed later, namely a procedure for partitioning the features of dataset into disjoint subsets, such that they exhibit simpler structures across the samples compared to the entire dataset. Specifically, given a prescribed number of partitions K, we propose to learn partitioning of the D features into K mutually exclusive subsets and K corresponding similarity graphs of size N N. Each similarity graph describes the pairwise affinities between all N observations when consid- ering only the corresponding subset of features. By creating
PPoorrm in Applied Math, Yale University, New Haven, CT, USA "Faculty Engineering, Bar Ilan University, Ramat Gan, Israel 'Department of Pathology, Yale University, New Haven, CT. USA "Interdepartmental Program in Computational Biol- ogy and Bioinformatics, Yale University, New Haven, CT, USA 'Department of Electrical Engineering. Yale University, New Haven, CT, USA. Correspondence to: <<crezpeter@e serezpeter@gmaii.comm gmail.com>>
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Miigh-Dimeniiioal Data
Underlying substructre 1
tSNE Embedding Based on All Features Colored by Blue Variable
Observed Data
Partioned
tSNE Embedding Based on Feature Partition 1 Colored by the Blue Variable
Feature Pertition
WW
Samples
Features
Underlying substructure
Feature Partition 2
ISNE Fmbedding Based Fealure Partition Colored by the Orange Variable
Colored by the Orange Variable
W
Samples
Samples
(a) The observed data and the traditional approach
(b) Our proposed approach
Figure 1. Illustration of our setting and proposed approach. (a) Simulated data consisting of two distinct substructures governed by independent latent variables: a closed loop (depicted in blue) and helical curve (depicted orange). Each substructure embedded within a specific (unknown) subset of the observed features. The iSNE emhedding, based all features, is presented the right in two panels: the top panel is colored according to blue variable, while the bottom panel is colored according to orange variable. (b) Our approach effectively divides the features into subsets (K=2), with each subset consistently capturing information from only one of the underlying structures (blue and orange). Using these features, the tSNE embeddings for each feature partition can be used to recover the driving latent variables. The structure of each embedding (illustrated the right), which is based solely subset of features, corresponds to one of the distinct latent variables (indicated by blue or orange).
separate graphs based on different sets of features, we can decompose complex data into simpler substructures, thereby better capturing their underlying patterns. Moreover, each feature subset describes a low-dimensional geometry, it can be embedded and visualized more effectively than the entire dataset using all features. Multiple low-dimensional em- beddings that capture different substructures in the data are often easier to interpret than single embedding in higher- dimensional space; see Figure 1. For further discussions on selecting the number of partitions K and validating that our approach leads to simplified data representation, we refer the reader to Appendix G.
larity graphs we propose minimizing an objective function that relies on a certain graph Laplacian- smoothness score. Our approach naturally extends the graph construc- tion step in common embedding and visualization tech- niques, such as ISNE and Diffusion Maps, by enabling the simultaneous learning of multiple graphs from adaptively chosen feature partitions. We analyze this objective function in a setup where multiple low-dimensional manifolds are embedded in nigh-dimensional space, possibly with partial dependence. We show that, in a suitable asymptotic regime with high dimension and large sample size, the minimum is attained only when the features are correctly partitioned into subsets that contain the individual embedded manifolds.
The setting where distinct feature subsets may contain unique geometric structures is widespread in applications. In hyperspectral imaging, different feature groups corre- spond to different wavelengths, which capture distinct chem- ical or physical phenomena the observed materials or en- vironment (Gowen et al., 2015; Khan et al., 2018). Similarly, in astrophysics, different spectral bands electromagnetic radiation serve feature groups in the data, capturing dis- tinct astrophysical phenomena such as interstellar extinction and gravitational waves (Indebetouw et al., 2005; Burke- Spolaor et al., 2019). In cellular biology and genomics, different groups of genes are associated with distinct cellu- lar processes (Sastry et al., 2019; Lamoureux et al., 2021), as exemplified in Section 5.2.
In Figure 1, we illustrate our approach on high- dimensional dataset where two distinct low-dimensional latent structures are embedded within different, unknown feature subsets (depicted in orange and blue). The tradi- tional (SNE embedding, constructed using all features, fails to reveal these underlying structures, resulting convo- luted representation. In contrast, method automatically uncovers and partitions the features associated with each latent structure, effectively disentangling the data. The re- sulting tSNE embeddings, generated separately for each par- tition, distinctly capture the corresponding latent variables, providing a more interpretable and structured visualization. Importantly, the latent variables governing each feature sub- set are not restricted single dimension but can represent
To find the best feature partitions and their associated simi-
2

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High--Diennsioall Data
more complex low-dimensional geometries, reinforcing the need for feature partitioning before emhedding.
of features forming the data are partially dependent (see Sections 4 and 5) scenario that cannot be addressed by existing product-manifold decoupling techniques.
2. Related Work
An alternative approach was introduced by (Van der Maaten & Hinton, 2012), who extended the iSNE algorithm to gen- erate multiple embeddings of the data. Their method con- structs a single affinity matrix from the high-dimensional data and produces several low-dimensional embeddings whose integration (via a specialized combination rule) best approximates the original affinity matrix. In contrast, our approach directly constructs multiple affinity matrices by partitioning the features into groups that capture distinct low- dimensional substructures. Each of these feature groups can be used to generate a separate embedding. enabling a more accurate representation of the underlying geometry-often obscured when relying single global affinity matrix.
Feature partitioning has been explored in bi- clustering (Dhillon, 2001; Kluger et al., 2003), where the objective is to simultaneously cluster features and observations into subsets with similar entries or corre- lated rows/columns. Additionally, traditional clustering techniques, such as k-means (Lloyd, 1982) and spectral clustering (Ng et al., 2001), can be adapted for feature partitioning by treating each feature vector as a sample in R.N. Our approach differs from such methods in that does not require features to have similar values or be correlated in order to be grouped together. Instead, we group features based on shared latent variables, which we identify from the inferred geometric structure across the samples. This enables more general and flexible partitioning of features into groups. Indeed, we demonstrate in Section 5.1 and Appendix D that conventional clustering and bi-clustering methods fail to correctly partition features in several experiments with both simulated and real data.
Finally, we mention Independent Subspace Analysis (ISA) and related techniques (Theis, 2006; Niu et al., 2010), which seek linear projections of the data into subspaces that are statistically independent or contain distinct structures. In high dimensions, these subspaces have many more degrees of freedom than the partitions learned by our approach, which can be prohibitive from computational and statisti- cal perspective (Bickel et al., 2018). Additionally, the ana- lytical properties of these methods are not well understood in high-dimensional settings, especially when the substruc- tures in the data are partially dependent. In contrast, our approach provides theoretical guarantees on accurate recov- ery of feature partitions in challenging high- nigh-dimensional scenarios, even under partial dependence between latent variables across partitions.
A closely related research area is unsupervised feature se- lection, which focuses on identifying important data fea- tures (Lindenbaum et al., 2021: Shaham et al., 2022). These methods typically utilize a similarity graph constructed us- ing all features to rank the features according to a Laplacian- based smoothness score. However, these methods only retain subset of the features, which may not represent all the latent variables of the data. Moreover, these methods do not specify which selected features correspond to distinct substructures in the data. In contrast, our approach does not lose any information since it retains all features in the data. Moreover, it separates the features into interpretable groups that can be embedded and visualized more effectively.
Bold symbols represent vectors or matrices. The d-th coordinate of a vector y is denoted by (y))a or ya. For any æ E RD' and w E IRF, denote the weighted norm by | = Eb wa(x))
Notations:
Another related line of work focuses on decoupling data from a produet-manifold (Zhang et al., 2021; He et al., 2023). This line of work is applicable to our setup if differ- ent feature groups are sampled from statistically indepen- dent manifolds. These methods attempt to deconvolve the eigenstructure of the graph Laplacian constructed using all the features to recover the graph Laplacians of the individual manifolds. One major limitation of such approaches is that the statistical error in the estimate of graph Laplacian-bast based quantities grows exponentially with the intrinsic dimen- sion (Singer, 2006). Hence, these methods are prone to large errors if the product manifold is governed by many independent latent variables. In contrast, our approach de- composes the product manifold into individual manifolds with low intrinsic dimensions, allowing for much more accurate construction of graph Laplacians for each manifold. Moreover, our approach supports cases where the subsets
3. Our Approach
This section presents the necessary background, motivation, and details of our proposed approach. First, Section 3.1, we review the construction of similarity graphs from data and introduce the key concept of data smoothness defined over these graphs. Next, in Section 3.2, we formulate an optimization problem that adaptively partitions features into disjoint subsets and constructs corresponding graphs to max- imize the total smoothness of the data. The proofs for this section are provided in Appendix I.I.
3.1. Traditional graph construction and the graph smoothness score
Given a set of observed data points yi...., VN E RD, common embedding and visualization techniques initially
3

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Highh-Dimensiona Data
construct graph representing their pairwise similarities. A popular choice of the graph affinity matrix W E [0, 1JNxN is a row-normalized Gaussian kernel defined by
Proposition 3.1.
The matrix W E [0, 1|NxN defined in (1)
is solution
arg min W e[o.1jNxN
J.W
(5)
exp(- 9. 1113/a)
i f (L) i=j
Was = D exT
0
subject to the constraints W., O. Σ Wa, 1 and وE= W., log Wa, I - -log(a) for all E NT. where : EN E from (1) are the minimum values that satisfy the entropy constraint.
for all i.j = I,...,NV where { C R4 represent bandwidth parameters controlling the effective neighbor- hood size around each point. Zeroing out the main diag- onal aligns with tSNE's graph construction step and also makes the resulting affinity matrix W more robust to noise (Karoui, 2010; Landa et al., 2021). Other embedding tech- niques, such as Diffusion Maps and Laplacian Figenmaps, construct the affinity matrix without zeroing out the main diagonal and with a single global bandwidth parameter.
Similar results appeared in (Cuturi, 2013; Van Assel et al., 2024) under slightly different constraints.
If the data is sampled from a Riemannian manifold and the bandwidth parameters e EN E R4 are fixed as con- stants (ignoring the entropy constraints), then the following proposition characterizes the relation between the objective function in (5) and the manifold's 's intrinsic dimension.
The tSNE algorithm determines the bandwidth parameters -1y...; CN from (1) by imposing an entropy constraint the rows of W. This constraint is given by
Proposition 3.2. Let M C R be smooth, compact, Riemannian manifold with intrinsic dimension dim(M) < D. Suppose Vı.....,uy UN E EM are sampled independently from a smooth non-vanishing density f over M, and let W be defined as in (I). Then, for all i E {l,...,N} and sufficiently small E1....,Ey EN E RR, ,,, we have
N
Wiy log Wa, S -log(a),
(2)
for i E N), where denotes predefined global neighborhood size parameter known as the perplexity, typ- ically set between 5 and 30. The (SNE graph construc- tion enforces this constraint by adjusting the bandwidth parameters } adaptively to the local sampling density. In contrast, other common graph construction techniques usually employ a global bandwidth constraint of the form 61 = _... cι discussed in (Singer et al., 2009).
N
Σ
Wes ll - 1زl as e: dim(M)) + 0(7)
(6)
N 2
Hence, for the affinity matrix W from (1) with sufficiently small bandwidth parameters, the objective function in (5) approximates the intrinsic dimension of the manifold multi- plied by the sum of bandwidth parameters. This quantity is smaller for manifolds with lower intrinsic dimensions, i.e.. simpler manifolds governed by fewer latent variables, or when the bandwidth parameters { are smaller.
Many feature selection methods (He et al., 2005; Linden- baum et al., 2021) utilize the affinity matrix for identifying a meaningful subset of features. In particular, given some affinity matrix W E [0, 1 that encodes the similarity between each pair of data points, these methods utilize a score of the form
3.2. Feature Partitioning and Multi-Graph Learning
S(W, d, (
Σ Was ((y))a- (g))aa) -,j=1
Given the dataset ......, NN E R., we propose to parti- tion the 1) features into K mutually exclusive subsets, each accompanied by corresponding N x N affinity matrix. In- tuitively, the data restricted to each subset of features should have simpler geometric structure than the data across all features combined. To find the feature partitions and their associated graphs, we propose to minimize the sum of graph smoothness scores from (4) over all feature partitions.
to measure the smoothness of the dth coordinate of the data over the graph. This score is often referred to as the Laplacian score (He al., 2005) for certain choices of the affinity matrix W. Summing this score over all coordinates, we define the graph smoothness score by
J(W, (UI
Σ W.rllu, - 11 k-=1
(4)
Concretely, let feature partitioning, where (()0) = 1 if the dth feature is used within the kth partition, and a²(²) otherwise. The feature partitions cover all features and are mutually ex- clusive; namely, they satisfy Σxn = 1 for all d e (1,..., D). The affinity matrices corresponding to the K
1) be feasible
The following proposition shows that the affinity matrix W
defined in (1) minimizes the graph smoothness score in (4),
subject to constraints of perplexity and stochasticity for each row (while zeroing out the main diagonal).
4

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Data
partitions are denoted by w(")
w(()) C |0, 1JNxN.
right-hand side of (11). Thus, our approach naturally ex- tends the traditional graph construction techniques discussed in Section 3.1 by forming multiple graphs from disjoint fea- ture partitions, which are optimized to minimize the total smoothness of the features across their associated graphs.
We now extend the graph smoothness score defined in (4) to support multiple feature partitions as
G((W (6)
K (h) Jk ( R==1 lty, y W
(7)
K
N
To further motivate Problem 3.3, consider data formed by concatenating K feature groups, where the features in each group were sampled independently from a different Rie- mannian manifold. In this case, under the optimal solution from Proposition 3.4, the objective function in (8) converges to a weighted sum of the manifolds' intrinsic dimensions (see Proposition 3.2). The weights depend on the corre- sponding bandwidth parameters {<H,s}. which are set to enforce the negative entropy constraints. However, for an incorrect partitioning - where features from different man- ifolds are mixed in each partition the intrinsic dimension of the data in each partition would be higher. Consequently, the required bandwidth parameters that satisfy the entropy constraints would be larger. Overall, we can interpret the optimization problem as dividing the feature space into par- titions whose intrinsic dimensions are as small as possible.
wa recalling that || w( Ex-1 (k) oa for any E
R Notably, when all the affinity matrices are the same (w
w((K)
W), then this score coincides with the score defined in (4), i.e., G([W(")) ) (6 Jkm (vr)) = (W, (..)
We define the following optimization problem to determine the feature partitions and corresponding affinity matrices.
Problem 3.3.
min (wil)
G(WW(() (k)
K Ik=1,
(0) IR=1 (
(8)
We now consider the task of solving Problem 3.3. A natu- ral strategy is alternating minimization, where the objective function is minimized over the graph parameters while keep- ing feature partitions fixed, and vice versa. The solution to each step of this alternating minimization is given explicitly by Proposition 3.4. Unfortunately, due to the binary nature of the feature partitions, this procedure is sensitive to local minima. To address this issue, in Appendix C we introduce regularized variant of the objective function (see Prob- lmm C.I) that produces soft assignment of features instead of hard assignments into partitions (see Proposition C.2). Our proposed algorithm (see Algorithm in Appendix C) solves several instances of the regularized problem sequen- tially, each with reduced regularization parameter, ini- tialized with the solution to the previous instance of the regularized problem. In the final step, the regularization parameter reaches zero, thereby minimizing the original unregularized problem. This sequence of solutions to the regularized problems is less likely to get stuck in a local minimum compared to solving the unregularized problem directly; see Appendix C for more details.
under the constraints Ex= - Wi
(k) = 1, E (((h) 1,
w.(k) = 0, and Σ}=1 W log (w/(k)
i = I....,,, k = 1....,,., K, and d (j S log(()), for is perplexity parameter.
(k)
is ......,,
1 1..... D. where a
Next, we characterize the solutions to Problem 3.3.
Proposition 3.4. There exists an optimal partitioning solution {w)(k)) jkmi and corresponding affinity matrices (W())) 1k=1 that solve Problem 3.3 and are the form
exp( exp(-113 111..--,,11 (.tts//ee))...
W/) = Engs exp (xp(-11) 1/ V V11li /ce,s)
iitj (9)
0
else
w = { if k= for some E ((d)
(0))
(10)
else
((d) = arg min S(W(k) (k) d, (y, I.
(11)
k)(
ford=1,.... i.. NN, where the bandwidth parameters { C IR. are the minimum values that sat- isfy the entropy constraints in Problem 3.3, and S is the I Laplacian-type score defined in (3).
4. Analysis
In this section, we analyze a variant of the feature partition- ing problem (see Problem 3.3) under a data generative model with K partially dependent subsets of features. We investi- gate the objective function landscape in a high-dimensional asymptotic regime and establish that its minimizer recov- ers the correct feature partitions. Additionally, numerical results in Appendix E demonstrate that the landscape of this variant closely mirrors that of the original problem. The
We see that the affinity matrix (+) is simply a row- normalized Gaussian kernel constructed from the features in the kth partition, analogously to the traditional construction in (1) using all features. Additionally, the dth feature of the data is assigned to the kth partition if it is smoother with respect to the affinity matrix (A) than the other affinity matrices, as measured by the Laplacian-type score in the
5

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hlgh-Dimensiona. Data
proofs for this section are provided in Appendix I.2. We define variant of the graph smoothness score as
Next, we derive the asymptotic value of the objective un- der a high-dimensional regime. We consider a genera- tive data model in which the observed space is based on subsets of features that exhibit partial dependence. Let Mi C , MK- C Rdd++ be latent smooth com- pact Riemannian manifolds with corresponding smooth, non-vanishing densities , The latent samples {a(") Ji=l E MM are independently sampled according to ʃa for 8 = 1...., K + 1. The observed data points, denoted by fy, LN E RR,, are constructed by
G ((wr JRmn
(k)
(6
( 1==1: (3r
(12)
K
11 - yル 11 (000)
En (k)
k=1
This variant adjusts the Laplacian- based score by normaliz- ing the portion related to each partition based on the average number of features used within that partition. This adjust- ment accounts for the changes made to the optimization problem, which we define next. As we will show, these modified formulations will retain key properties of the orig- inal problem.
ut ((x())r .......!!!) (1) ER.
(15)
v. p(s)
x x
(k+1)
E ERD
8
K,
for i 1, 1,...; N1, where D D= K
D.. and the entries of p(+) E DR (d2 are independently sampled from 1/D.) for 8 = I. K.
Building on this score, we propose to analyze simplified variant of Problem 3.3, aimed at identifying the feature partitions and their associated affinity matrices. This ver- sion adopts a regularized minimization framework that in- corporates the negative entropy constraint directly into the objective, enabling more tractable analysis.
To establish direct correspondence between each partition (k) and the true K partitions used in the construction of the observation space, we denote w()) = (w.kk1)
w (k.
for h: = 1,..., K. We define the relative proportion with (k,s) iD, + ps (k)
Problem 4.1. Consider the optimization problem defined by
DD respect to each true partition by > w/
(0, 1), for any k s E {1..., K}, where all s.
kkml Ek (k) = 1 for
ā @(W DiEn (W) (v.)
min (w(t)) (wr)), (00m).
(13)
The next theorem characterizes the objective function of Problem 4.1 in a high-dimensional asymptotic regime where D,N + oo and D/ /og((>)) + oc. We assume that the relative size of each feature subset satisfies Dz/D) - 3,
K
N
(
(k)
log (w/(A))
+e
k=1v==
(0,1) for any E {I,...,,K, where B E (0, 1)x and
with the following constraints Ek=1 Wd
(k)
1.
Ex 3. 1
Σn W/() w.(0) (R) O. for i 1, 1,..., N, k
Theorem 4.3. There exists f) S 1 such that for any e E and (k) E -K- E) any partitioning so- lution {wikk) (obeying Problem 4. 1. constraints) satisfies
1,... K and d = I,..,, D.
We characterize the affinity matrices that minimize this objective in the following corollary.
(1) G (a((((")) (.00). .v.it (16)
min w eN
Corollary 4.2. Let (k) be partitioning that satisfies the constraints in Problem 4.1. Then, graph affinity matrices
that minimize (13) while fixing the partitioning parameters (a)() (K) } are
K Σ
(h) log (og( )) + K Klog(N- - 1)
+e
k=
19,- 91,12 (K)
K
dim(MM++1)
Ps
(k)
exp
log
(17)
w:(k)
iitj
N
2
-= Pi Br.
K
(K)
11. 19..
(14)
MN exp
".(1/D)) (K)
K dim(Mas)
p!!
log
else
E1=1 Pt. 3.
K
(K)
k,a=1
for i,j = L,...,N N and
K.
K+1
dim(MM) log(TT))
+K
Σ aml
ho((.)
+ +O(ve),
2
Note that the effective bandwidth parameter of each (*)) adapt according to the number of features in its correspond- ing partition (A) for k- 1 1,...,K. K.
fa(x) log f. fz())dz is the differ- where h he(fa) - ential entropy of the density Sa over Ms-
6

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High--immnniion Data
Data Composed of Two Independent Substructures
Table I. Performance of different methods for partitioning the fea- tures for the two scenarios shown in Figure 2. The partitioning error is the number of coordinates assigned incorrectly, averaged over 100 randomized experiments, and the standard deviation is shown in parentheses. The correct partition should separate the first three coordinates from the last thrce, thereby correctly capturing the two ellipsoid structures.
Data Compased of Two Partially Dependent Substructures
METHOD DATA DATA
INDEPENDENT
PARTIALLY DEPENDENT
SPECTRAL
1.85
1.95
CO-CLUSTERING
(0.91)
(0.8)
SPECTRAL
1.99
2.15
BI-CLUSTERING
(0.59)
(0.78)
91
K-MEANS
1.77
2.22
(ON FEATURES)
(0.55)
(0.74)
(a)
SPECTRAL CLUSTERING
1.71
2.2
(ON FEATURES)
(0.94)
(0.73)
Absolute Value of Correattinn Matrices
FP (OURS)
0.
0.
V1
ALGORITHM I
(0.)
(0.)
V2
Y2
91
74
y4
ys
ys
To conclude, we proposed a variant of the feature partition- ing problem in Problem 4.1 and analyzed its loss landscape in an asymptotic regime. We considered data- mata-generating process where the features are composed of K partially dependent feature groups, making the partitioning task non- trivial. Finally, we showed that in this nontrivial case, the loss is minimized when the partitioning solution aligns with the ground truth when K = 2. In Appendix E, we show the close resemblance between the loss landscapes of the exam- ined problem and Problem 3.3 using synthetic dataset.
36
V1 ys
(b)
Figure 2. Product of 2-dimensional ellipsoids. (a) Simulated data including N = 1000 samples in R², where the first three coordi- describe one ellipsoid and the last three describe another, and hoth parameterized by polar angles depicted by colored ellipses. the first scenario, the ellipsoids are independent (Top). con- trast, in the second, they are partially dependent (Bottom) since one polar angle is shared between the two ellipsoids (the black ellipse). (b) The absolute value of the feature-featur correlation matrix of the two datasets. For clarity, we slightly abuse notation by using Va. or correspondingly Ja. to denote the dth coordinate (i.c., feature) of the data.
5. Experiments
This section highlights our approach and its advantages through synthetic and real data. In Section 5.1, we illustrate and quantify its effectiveness in controlled environment using artificial data. Next, in Sections 5.2 and 5.3, we show the applicability of our approach to two real-world high- dimensional biological datasets, yielding enhanced visual- izations that are consistent with known biological processes. Finally, in Appendix D, we use video data to demonstrate that our approach can enhance the ability to visualize and correctly analyze complex datasets.
Evidently, only the first two terms in (17) are affected by the feature partitions, while the rest depend on the manifolds' properties, and their densities. In the following theorem, we show that the minimizer of (17) in the case of two partitions (K = 2) accurately separates the data features as E > O.
Theorem 4.4. Let = 2, and define f: (0, 1)² + TR by
k dim( (Mn(MM+1) log
Σ 5= Ps
(k)
f(1)
(18)
2
K
Pr 3r
(K)
5.1. Product of 2-Dimensional Ellipsoids
-=
dim( Mss)
Pe
(M)
This experiment demonstrates the effectiveness of our ap- proach decomposing the data into different substructures in a controlled environment using synthetic datasets. We simulated two datasets in R6; one with two independent feature subsets and another with partially dependent ones, and the task is to retrieve these subsets (K = 2). In the independent case, samples are drawn independently from two rotated 2D ellipsoids in R3 and their coordinates are
log
1
2
Σ K
Ee=
Pt
(,)8)
where Pi Pı and
(1)
P2
(1)
p2 and therefore p1
Then, the limiting minimizer (pi,p)) = lim.-0 arg min poe f(p1,22) is
1- p1 P2
1
either (0, 1) or (1,

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dithhnionnn Data
ISNE Embedding based on Partition 1 Genes
ISNE
All Genes
Partition Genes
3x
(Ours)
IC-PMI
LDLE
2x
Multi-ISNE
All Features
Error
FP Features (Ours)
DC
G1
10"1
6x
G2M
K-Nearesl Nelghbors
(a)
(b)
Figure Partitioning the genes scRNA-see data discover distinct salient cellular processes. (a) figure includes iSNE embeddings using all genes (left) versus genes from partition (middle) and partition 2 (right). Top: Cells colored by cell type, with partition capturing the LD/UD to DC developmental trajectory. Bottom: Cells colored by cell cycle phase, with partition revealing cycling progression. (b) A quantitative comparison of embeddings generated by different algorithms, assessing their correspondence with the two latent processes governing the data via k-nearest neighbor error. The results show that our partitioning approach most effectively reveals the underlying structure, with each process captured distinct partition. See Appendix F.2 for details on the error metric.
stacked form vectors in R In the partially dependent case, the generating process is the same, except that one of the polar angles is shared between the ellipsoids. The inde- pendent (Top) and partially dependent (Bottom) datasets are visualized in Figure 2(a), and their correlation matrices are shown in Figure 2(b). See Appendix F.1 for further details.
within each cell after standard processing is applied, includ- ing variability-based feature selection; see Appendix F.2. The preprocessing is similar to that employed in (Qu et al., 2024). In that study, the authors examined the genes through gene similarity graph derived from the cells' affinity matrix and their gene profiles. In contrast, our approach partitions the genes according to their graph structure, generating a separate graph for each subset. To motivate the use of our approach, we note that each of these processes is associ- ated with different subsets of genes, many of which well-characterinn (Tirosh et al., 2016).
In Table we assess the performance of several methods adapted to partition the features in the scenarios de- scribed above. The recorded error is the number of coordi- nates (out of six) assigned incorrectly, averaged over 100 randomized experiments. The results demonstrate that tra- ditional clustering or bi-clustering approaches cannot be utilized to solve the problem we consider here. Indeed, while these approaches perform slightly better in the in- dependent case than the (more challenging) dependent case, they still incur substantial errors in both cases. In contrast, our proposed approach consistently recovers the correct partitions across all experiments.
Using our approach, we partition the genes into two groups (K = 2). In Figure 3, we compare the tSNE embedding based on features with separate tSNE embeddings based on each extracted partition. The embedding based on all genes reveals the cell rype development (top) but not the cell cycle phase progression (bottom). In contrast, the partition- based embeddings reveal both processes: partition cap- tures the cell type structure, while partition 2 reveals the cell cycle structure. We further validate these findings in Appendix F.2. First, Figure demonstrates similar results using alternative embedding techniques, underscoring the importance of partitioning. Then, in Figure 10, we repeat the task with 10,000 features. While the added genes may introduce variability, our approach still recovers key sub- structures. Finally, in Figure I1, we repeat the experiment on a different biological dataset with similar characteristics and observe consistent results.
5.2. Dermal scRNA-seq Data
In this experiment, we demonstrate that our approach effec- tively separates co-occurring biological processes in single- cell -NA-seqqun data, enabling clear visualization of each process, thereby improving scientific discovery capa- bilities. Specifically, we analyze embryonic dermal cells from mouse skin (Qu et al., 2024), which exhibit two inter- twined processes: cell cycle progression (G1, G2M, and S phases) and cell type development (from lower dermal (LD) to upper dermal (UD) to dermal condensate (DC) cells).
In Figure 3(b), we quantitatively compare the embeddings generated based on our extracted partitions with those pro- duced by alternative techniques. The evaluated approaches
The dataset comprises N = 5572 cells and D = 5000
features, each representing the expression level of a gene
8

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High--Diennsionll Data
include: 1) iSNE embedding using all features; 2) two LSNE embeddings based on our partitions (<FP'); 3) two embeddings of IC-PML (He et al., 2023); 4) single embed- ding of LDLE (Kohli et al., 2021); 5) two embeddings of Multi-tSNE (Van der Maaten & Hinton, 2012); 6) raw data features; and 7) raw data features after partitioning ('FP Fea- tures'). For each approach, we assess the correspondence between the structure of the provided embeddings and the latent variables. Specifically, the metric assesses how well the latent variables are reflected within the local neighbor- hoods of the embeddings for different neighborhood sizes (k- Ik-Nearest Neighbors), providing a comprehensive view of the embeddings' quality; see Appendix F.2 for further details. Our approach consistently yields the lowest error, outperforming existing methods when evaluated either on the raw feature partitions or on their tSNE embeddings.
In Figure 12, we compare the tSNE embeddings generated based on each group with standard iSNE emhedding based on all features. The standard embedding provides a single visualization where both latent variables are partially visible. Specifically, the circadian cycle is reflected by four clusters corresponding to the four sampling time points, although the cyclic structure is less evident. In contrast, the embed- ding based on partition 2 reveals both the clusters and the cyclic structure. Additionally, while zonation is partially visible within each cluster in the standard embedding, it is less evident than the clear, progressive pattern seen in partition I's embedding. The latter aligns with the zonation layers effectively. These results demonstrate the benefit of our approach in revealing distinct latent variables.
6. Discussion
Importantly, the partitions obtained by our approach are consistent with known biological phenomena: partition 1 includes the genes Sox2 and Foxdl, expressed in the DC cell type, and the genes Ptchl and Lef1, expressed in both UD and DC cell types (Qu et al., 2022). In contrast, partition 2 contains all 86 cell-cycle genes from the Seurat R package that were retained in our dataset after preprocessing (Tirosh et al., 2016). Overall, approach effectively separates the genes according to the two underlying biological processes.
This paper presents novel computational framework to partition the features of a high-dimensional dataset into sub- sets with simpler underlying structures. Embedding and visualizing the data using the features of each subset can ef- fectively reveal these simple structures, which are obscured in the embedding that uses all the features. We demon- strate the effectiveness of our approach both analytically and empirically using simulated and real-world data, even when the features consist of partially dependent subsets. In Appendix G, we discuss practical considerations, e.g., the selection of the number of feature partitions. Addition- ally, we include an experiment on a subset of the COIL-20 dataset in Appendix H. demonstrating the effectiveness of our approach in scenarios where the feature separability assumption may not hold.
5.3. Liver seRNA-seq Data
In this experiment, we demonstrate our approach on biolog- ical data whose features are transformed to enable effective partitioning. Specifically, we consider single-cell RNA- sequencing liver lobule dataset (Droin et al., 2021), charac- terized by two independent latent variables, with multiple genes influenced by both of them. Here, the raw features (genes) cannot be partitioned into partially fully inddpen- dent subsets, making a suitable transformation necessary.
Our approach addresses some of the criticisms of low- dimensional embeddings raised in (Chari & Pachter, 2023). In particular, it enables more accurate embedding of sub- structures with low intrinsic dimensions through the pro- posed partitioning, as demonstrated in our experiments. While there is no guarantee that these substructures can be faithfully visualized in two or three dimensions, the result- ing partitions remain valuable for range of analytical tasks beyond visualization. Thus, by focusing on partitioning the data into simpler structures, our approach is inherently less susceptible to such criticism.
The dataset comprises N = 6889 cells and D = 2000 features, each representing the expression level of a gene within each cell after standard processing is applied; see Appendix F.3 for details. The dataset's structure is governed by two latent variables: spatial zonation, associated with the cells' locations along the liver layers (1-8); and the circa- dian cycle, associated with the time each cell was sampled (ZT 0, 6, 12, and 18) within a hour cycle.
We identify several promising directions for future research. First, developing fully automated methods to determine the optimal number of partitions K would enhance the practi- cality of our approach. Second, exploring more efficient op- timization techniques for Problem 3.3 and deriving convex relaxations could significantly improve computational effi- ciency and solution quality. Finally, extending the method to account for uninformative or nuisance features presents important avenue for broadening its applicability.
Droin et al. (2021) modeled the expression of each gene across cells based on the cells' liver layer and sampling time, with prior knowledge incorporated into the model. They showed that the two latent variables govern overlapping subsets of genes. To address this challenge, we decorrelated the features using principal component analysis (PCA), standard preprocessing step in the field (Andrews et al., 2021). We then applied our approach to the transformed data, partitioning the new features into K = 2 groups.
9

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimenniooal Data
Acknowledgements
Cuturi, M. Sinkhorn distances: Lightspeed computation
of optimal transport. Advances in neural information processing systems, 26, 2013.
The research conducted by O.L. funded by the MOST grant 207892. The research conducted by Y.K. is funded by the National Institutes of Health (R01GM131642, UMIPA051410, R33DA047037, U54AG076043, U54AG079759, UOIDA053628, P50CA121974).
Dhillon, I. S. Co-clustering documents and words using
bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 269-274, 2001.
We would like to thank Peggy Myung. Ruiqi Li, Rihao Qu, and Junchen Yang for their valuable help with understanding and preprocessing the biological datasets used this study.
Droin, C.,, Kholtei, J. E., Bahar Halpern, K., Hurni, C., Rozenberg, M., Muvkadi, S., Itzkovitz, S., and Nacf, F. Space-time logic of liver gene expression at sub-lobular scale. Nature metabolism. 3(1):43-58 2021.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
El Ghaoui, L. and Gueye, A. A convex upper bound on the log-partition function for binary graphical models. In Proc. NIPS, 2008
Gowen, A. A., Feng, Y., Gaston, E., and Valdramidis, V. Recent applications of hyperspectral imaging in microbi- ology. Talanta, 137:43-54, 2015.
References
Andrews, T. S., Kiselev, V. Y., McCarthy, D., and Hemberg, M. Tutorial: guidelines for the computational analysis of single-cell ma sequencing data. Nature protocols, 16(1): 1-9, 2021.
He, J., Brugère, T., and Mishne, G. Product manifold learn- ing with independent coordinate selection. In Topological, Algebraic and Geometric Learning Workshops 2023, pp. 267-277. PMLR, 2023.
Belkin, M. and Niyogi, P. Laplacian eigenmaps for di- mensionality reduction and data representation. Neural computation, 15(6):1373-1396 2003.
He, X., Cai, D.,, and Niyogi. P. Laplacian score for feature selection. Advances in neural information processing systems, 18, 2005.
Bickel, J., Kur, G., and Nadler, B. Projection pursuit in high dimensions. Proceedings of the National Academy of Sciences, 115(37):9151-9) 2018
Hein, M., Audibert, J.-Y., and Von Luxburg, U. From graphs to manifolds-weak and strong pointwise consistency of graph laplacians. In International Conference on Compu- tational Learning Theory, pp. 470-485. Springer, 2005.
Blau, Y. and Michaeli, Non-redundant spectral dimen- sionality reduction. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2017, Skopje, Macedonia, September 18-22, 2017, Proceedings, Part 1 10, pp. 256-271, Springer, 2017.
Indebetouw, R., Mathis, J., Babler, B., Meade, M., Watson, C., Whitney, B., Wolff, M., Wolfire, M., Cohen, M., Bania, T., et al. The wavelength dependence of interstellar extinction from 1.25 to 8.0 pm using glimpse data. The Astrophysical Journal, 619(2):931, 2005.
Spokaor, S., Taylor, S. R., Charisi, M., Dolch, T., Hazboun, J. S., Holgado, A. M., Kelley, L. Z., Lazio, T. W., Madison, D. R., McMann, N., al. The astro- physics of nanohertz gravitational waves. The Astronomy and astrophysics review, 27:1-78, 2019.
Karoui, N. E. On information plus noise kernel random matrices. Annals of Statistics, 38:3191-3216, 2010.
Khan, M. J., Khan, H. S., Yousaf, A., Khurshid, K., and
Abbas, A. Modern trends in hyperspectral image analysis: A review. leee Access, 1:14118-1411 2018.
Chari, T. and Pachter, L. The specious art of single-cell ge- nomics. PLOS Computational Biology, 19( 2023.
Kluger, Y., Basri, R., Chang, J. T., and Gerstein, M. Spectral biclustering of microarray data: coclustering genes and conditions. Genome research, 13(4):703-716, 2003.
Coifman, R. R. and Lafon, S. Diffusson maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Kohli, D., Cloninger, A., and Mishne, G. Ldle: Low distor- tion local eigenmaps. The Journal of Machine Learning Research, 22(1):1291 1211--19977 2021.
Cover, T. M. and Thomas, J. A. Elements of Information Theory. John Wiley& & Sons, 1991.
10

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimennional Data
Lamoureux, C. R., Decker, K. T., Sastry, A. V., McConn, L.., Gao, Y., and Palsson, B. O. Precise 2.0-an expanded high-quality ma-seq compendium for escherichia coli k-12 reveals high-resolution transcriptional regulatory structure. BioRxiv, pp. 2021-04, 2021.
Qu, R., Cheng, X., Sefik, E., Stanley III, J. S., Landa, B., Strino, F., Platt, S., Garritano, J., Odell, I. D., Coifman, R., et al. Gene trajectory inference for single-cell data by optimal transport metrics. Nature Biotechnology, PP. 1-11, 2024.
Landa, B., Coifman, R. R., and Kluger, Y. Doubly stochas- tic normalization of the gaussian kernel is robust to het- eroskedastic noise. SIAM journal on mathematics of data science, 3(1):388 413, 2021.
Rockafellar, R. Convex analysis. Princeton Mathemalical Series, 28, 1970.
Sastry, A. V., Gao, Y., Szubin, R., Hefner, Y., Xu, S., Kim, D., Choudhary, K. S., Yang, L.., King, Z. A., and Palsson, B. O. The escherichia coli transcriptome mostly consists independently regulated modules. Nature communica- tions, 10(1):5536, 2019.
Lederman, R. R. and Talmon, R. Learning the geometry of common latent variables using ceernatinn-diffsioon Applied and Computational Harmonic Analysis, 44(3): 509-536, 2018.
Shaham, U., Lindenbaum, O., Svirsky, J., and Kluger, Y. Deep unsupervised feature selection by discarding nui- sance and correlated features. Neural Networks, 152: 43 2022.
Lindenbaum, O., Yeredor, A., and Salhov, M. Learning coupled embedding using multiview diffusion maps. In Latent Variable Analysis and Signal Separation: 12th International Conference, LVA/ICA 2015, Liberec, Czech Republic, August 25-28, 2015, Proceedings 12, pp. 127- 134. Springer, 2015.
Singer, A. From graph to manifold laplacian: The con- vergence rate. Applied and Computational Harmonic Analysis, 21(1):128-134 2006.
Lindenbaum, O., Shaham, U., Peterfreund, E., Svirsky, J., Casey, N., and Kluger, Y. Differentiable unsupervised feature selection based on gated laplacian. Advances in neural information processing systems, 34:1530-1542, 2021.
Singer, A., Erban, R., Kevrekidis, G., and Coifman, R. Detecting intrinsic slow variables in stochastic dynamical systems by anisotropic diffusion maps. Proceedings of the National Academy of Sciences, 106638):16000-16695 2009.
Lloyd, S. Least squares quantization in pem. IEEE transac- tions information theory. 28(2):129-131 1982.
Theis, F. Towards general independent subspace analysis. Advances in Neural Information Processing Systems, 19, 2006.
Mclnnes, L., Healy, J., and Melville, J. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 1rXiv:/802.03422 2018
Tirosh, I., Izar, B., Prakadan, S. M., Wadsworth, M. H., Treacy, D., Trombetta, J. J., Rotem, A., Rodman, C., Lian, C., Murphy, G., et al. Dissecting the multicellular ecosystem of metastatic melanoma by single-cell ma-seq. Science, 352((282) 189-199)18999 2016.
Nene, S. A., Nayar, S. K., and Murase, H. Columbia object image library (coil-20). Technical Report CUCS-005-96, Department of Computer Science, Columbia University, February 1996.
Van Assel, H., Vayer, T., Flamary. R., and Courty, N. Snekhorn: Dimension reduction with symmetric entropic affinities. Advances in Neural Information Processing Systems, 36, 2024.
Ng, A., Jordan, M., and Weiss, Y. On spectral clustering: Analysis and an algorithm. Advances in neural informa- tion processing systems, 14, 2001.
Niu, D., Dy, J. G., and Jordan, M. I. Multiple non-redundant spectral clustering views. In Proceedings of the 27th international conference machine learning (ICML-10),
Van Der Maaten, L. Accelerating t-sne using tree-based algorithms. The journal of machine learning research, 15 (1):3221-322 -245,, 2014.
pp. 831-8388 838, 2010.
Van der Maaten, L. and Hinton, G. Visualizing data using I-sne. Journal of machine learning research, 9(11), 2008
Osher, S., Shi, Z., and Zhu, W. Low dimensional manifold model for image processing. SIAM Journal on Imaging Sciences, 10(4):1669-1699) 2017.
Van der Maaten, I. and Hinton, G. Visualizing non-metric similarities in multiple maps. Machine learning, 87:33 55, 2012.
Qu, R., Gupta, K., Dong, D., Jiang, Y., Landa, B., Saez, C.,, Strickland, G., Levinsohn, J., Weng, P.-l., Taketo, M. M., et al. Decomposing a deterministic path to mesenchymal niche formation by two intersecting morphogen gradients. Developmental cell, 57(8):0033-11 2022.
Wainwright, M. J. High-dimensional statistics: A non- asymptotic viewpoint, volume 48, Cambridge university press, 2019.

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hligh-Dimensione Data
Zhang, S., Moscovich, A., and Singer, A. Product mani- fold learning. In International Conference on Artificial Intelligence and Statistics, pp. 3241-3249. PMLR, 2021.
12

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- High--Dimensional Data
A. Code Repository
The code for this paper is in http:///ss/.tt....///////p/////a
B. The Algorithm
Algorithm Feature Partitioning
1: Input: Data samples V...... VN E IR' Number of partitions K E N; Number of iterations T.
2: Initialize the feature partition vectors w (K) according to
(K)
for k = i...., K; d = .....
Σx (()))
where (1), ..... ((K) iid. Uniform[0, 1|p.
3: Set 8 + mit according to (24).
4: for = 1 to 7 do
5: if = then
6: Set 5 +- O.
7: end if
8: while the score Grey from (19) decreases do
(a) Update the affimity matrices (1)
( E [0. 1] NxN according to (9).
9:
(b) Update feature partition vectors w()) (() [0, 1] according to (21).
11:
(c) Compute the new score Greg according (19).
12: end while
13: Update 5 <- 8/2.
14:
end for
15:
Return (1) (K),
Note: In our simulations, we run this algorithm multiple times with different random initializations and return the solution with the lowest score.
C. Algorithmic Details
This section presents an algorithm for solving the feature partitioning problem described in Problem 3.3. The algorithm solves sequence of regularized versions of this problem sequentially, gradually reducing the regularization until the problem aligns with the original problem. In this section, derive the algorithm update formulas, compare it to naive solution to Problem 3.3, and analyze its computational complexity. The proofs for this section are given in Appendix I.3.
A direct approach for solving Problem 3.3 naturally arises from Proposition 3.4 in the form of an alternating minimization procedure, by minimizing the objective function over the partition parameters while keeping the affinity matrices fixed, and vire-versa. However, such a technique is susceptible to converge to local minima due to the binary nature the partition parameters, illustrated in Figure (rightmost column). order address this issue, we define regularized version of the problem that allows soft partitions (k) C [0, 1j2 The new objective function uses an entropic regularization term for the weights (k) with regularization parameter e Rt. Specifically, define the regularized objective function as
(k) Greg(5, (1) 1 Ik=1 (K))) (V. = G([W }. (0)0)) (
(19)
D 1=
K
+5 (llog(K)
(
log(o!!))
where G is the objective function of the unregularized problem defined in (7).
The new regularized optimization problem is defined as follows.
13

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Highh-iienniionl Data
The Loss Landscape with the Partitioning Parameter Updates The Partioning Solution at the Beginning of iteration t, Black Arrows= Parameter Updates)
(White=
w
Loss:
meng (Wit), (w(k), (xi))
Giinni)) {w(k), (vi))
Iteration:
t=1
t=2
6
6init
6 6init/2
6 6mn/44 (w) (to =t= 2
(w w ) (w) fiittt) w )
(t - w w/(=1))
(ws csfinitt
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
w (1)
w
w
w
(w
w = (w) [mit) (
(wfft-1), w 1))
(woft
w 2))
(nit)) finit)
0.6
0.0
(
(
(
(
Figure 4. An experiment comparing the landscape and iterations of Algorithm (first three columns) with naive alternating minimization technique based Proposition 3.4 (rightmost column). On the left, each column shows the loss landscape of regularized loss in each iteration E (1....,3). 3). where the partitioning updates in steps 5-8 are drawn on top of that. Specifically. in the first row, the loss landscape consists of varying values of the first two partition coordinates, while the last step. The bottom row is similar, but considers varying values for the third and fourth coordinates, while constraining the first two. The provide
constrained to be the initial solution this
black arrows depict the partitioning parameter updates applicd throughout each algorithm iteration. In the rightmost column, similar visualization for the alternating minimization based on the unregularized objective function. The data is composed of N 400 samples in D dimensions that consist two concatenated circles, meaning that the correct solution (1))) (0, 0, 1, 1). In the regularized case (Iefft), after the algorithm converges for specific configuration f, its updated parameter values assigned w ((+1) as described Algorithm
Problem C.1. Let 8 R4. Consider the following minimization problem
min K Lmm (000)*
Cd ( (k) KK
1K=11 (6)
(20)
with the constraints: >K W/ I....,K K, and I.....D. D.
= 1. M
(K(0) = 1, (K( and E3 (h) log isj < log(a)))ori ,,...,,
Our proposed algorithm (Algorithm 1) aims to solve the original problem (Problem 3.3) by solving a sequence of the regularized versions of the problem (Problem C.I) with diminishing regularization until the two problems align. Specifically, it begins by solving Problem C.1 for some 8 = 8intt, and then uses its solution the initialization point for solving the regularized problem with reduced 6. This procedure repeats itself with the lowered value of 6. In the last iteration, the regularization parameter is set to zero match the unregularized problem.
The entropy regularization modifies the loss landscape to penalize hard partitioning solutions and is intended to prevent rapid convergence to poor local minima characterized by hard partitions, as discussed in the context of the unregularized objective the beginning of the section. Specifically, for any d (1,..., D). hard assignment (55 (k) ] k== C (0, 1) yields zero
14

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hligh-Dimensional Data
entropy, i.e., Σx=1 Wi log wa (8) In contrast, the regularization favors soft assignments (5 the uniform assignment Wid (k) 1/K for all & f1,.... }} and d E (I.....D) attaining the minimum negative entropy of llog K) (See Theorem 2.6.4 in (Cover & Thomas, 1991)).
] C CO, 1),, with
We begin by describing the problem's solution for each 8. Given that there are two sets of parameters-the feature partitions (=) and their corresponding affinity matrices [ propose an alternating minimization approach to solve the regularized problem for each 6. Specifically, the method alternates between minimizing the objective function over the affinity matrices while keeping the partition weights fixed and vice versa. The solution to each step in the alternating minimization procedure is described by the following proposition, whose proof be found in Appendix I.3.
Proposition C.2. Let 6 2 O, (w(()) kk= C [0, [)
? be a partitioning weights and { (R)
Jk=1 C [0, 1] N be affinity
matrices that satisfy the constraints of Problem C.I.
Define { (k)m C [0,1] as in (9) based on (w) km and {w((k)n lkml by
Eis W!bh ((yi)a (30)))
(1))aa
K
Eis W:(g) ((yi)d (w))aa²)
(k)= exp W
Σ
exp
(21)
6
5
Then, we have that
(W(k)e)
= arg min Greg (6, (W (K) (W
JEEn (K) (y.))
(22)
arg min Greg (6, (W(K)) Ik- (0) (y.1
(23)
1000))
We now turn to the choice of the initial regularization parameter, S which determines the starting point of the sequential procedure. In the following proposition, we propose to select ôiit such that the regularized objective evaluated at the uniform partitioning - i.e. (k) 1/K for all d E (1...., D) and (1..... _)- guaranteed to be less than or equal to its value at any hard partitioning.
Proposition C.3. Let (w) 10, be soft uniform partitioning, i.e. (k) 1/K, and let |K be the corresponding affinity matrices from Proposition C.2. Let {w(k)) 1K=1 C [0,1] and [W( be the optimal partitioning solution as discussed in Proposition 3.4.
Define
G((W
(K)
KK
( (K)
Ik- 1 (U
Senit
jk 1
(24)
D log((s
Then, for any hard partitioning solution (w)1k) LK pk=1
C 10,1) 1 and any corresponding affinity matrices { (k)
jk=1
have:
Greg(dinst,
W (k)
( K 1k=1 IKED (1)) S Greg(6mmit ( (K (w(t) 1k=1 JKED (
(k)
(25)
The proof of Proposition C.3 can be found in Appendix I.3.
In Algorithm 1, we outline the steps of our proposed feature partitioning procedure based on Propositions C.2 and C.3. In Figure 4, illustrate the convergence behavior of proposed optimization procedure versus naive alternating minimization of the unregularized objective function (in Problem 3.3). As observed from the rightmost column, the latter quickly converges to an incorrect solution. However, as seen from the leftmost column, the regularization guides the solution towards a uniform partition at t 1. As the regularization parameter ((t) decreases (second and third columns from the left), the solution gradually shifts towards the correct partition.
Determining the Bandwidth Parameters. The expression of the affinity matrices in Proposition C.2 based on { C o0), which are chosen to be the minimal values that satisfy the entropy constraints K.N
E==1 W log ((())= S - log(a) for all = I,..., , K and I,....N.. N). Our approach for setting the bandwidth
15

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High--Dienniinal Data
parameters is very similar to the one used in iSNE, albeit adapted for weighted Euclidean distances (appearing in the form of the affinity matrices in Proposition C.2) instead of standard Euclidean distance. Specifically, we use a -ikch search to set the bandwidth parameters to satisfy the entropy constraints, as described below.
As the bandwidth parameters are computed independently of each other, we focus on specific cg,, for some i E N and & E {I..... K.. The behavior of the entropic function >, w log W:('"* with respect to Ck.i can be characterized by Lemma 1.1 in Appendix 1.1 (which is used for the proof of Proposition 3.1 and Lemma I.3), where we use the notation A lyy, y (l for j = 1, ,..... N. Specifically, Lemma I.1 indicates that this entropic function is non-increasing in éR,i and bounded in the interval log((A NN - 1), log( where
G.5
1.j
i = Kij E (I,1.,,NN/( : lly: بyllwa
min ll., - y Ho|lw0 H/- tyf
(26)
Moreover, it establishes that as EN,i + 0 the entropy converges to - (oog(āx,), whereas as EXYi + oo it tends to - log(N - 1). Since the entropy is monotonic and bounded with respect to this parameter, employ a binary-search-like iterative procedure to efficiently approximate the appropriate value of cx to within small error, similarly to the one used in tSNE,
Computational Complexity. We now analyze the computational complexity of the parameter updates shown in Algorithm 1, which are based on the expressions defined in Proposition C.2. Consider a dataset with N observations in RD, where the features are partitioned into K subsets. The computational complexity of updating the K partitions and their corresponding affinity matrices using our approach is O(K (LKN2D) D), based on the next proposition.
Proposition C.4. Let the data consist of N data points in RDD Then, the computational complexity of obtaining the purtitioning weights {w)(k)+ k=
)k=1 and the affinity matrices (W(k)) He= as defined in Proposition C.2, is O(K
Its proof can be found in Appendix I.3. For reference, the computational cost of the affinity matrix construction in tSNE is ONNDD). Hence, the computational complexity of our approach incurs an additional factor of K, which is typically small. Nonetheless, may be significantly slower than tSNE due to the iterative procedure we employ for solving our optimization problem.
To enhance scalability, we also describe implementation that exploits low-rank approximation of the data, which can considerably reduce the running time for large datasets. Specifically, we approximate the data by truncating its singular value decomposition (SVD) to S < min(N, D) leading components, and then use this compact representation to speed up computations. Subsequently, the computational complexity of updating the K partitions and their corresponding similarity graphs will reduce to (S + D)); see the following proposition.
Proposition C.5. Let the data consist of N data points in IR. Suppose the data is given in the form of a singular value decomposition (SVD) approximation of rank S < N, D. Then, the computational complexity of obtaining the partitioning weights (w)())) k j and the affinity matrices { (6]=) LK Jk=p as defined in Proposition C.2, is O(K(S2N N2 + D)))
Its proof can be found in Appendix I.3.
D. Additional Experiment Involving Two Concatenated Views of Rotating Figurines
We demonstrate the effectiveness of our approach in disentangling three simultaneously occurring processes, each associated with distinct rotating object in shared scene recorded by two separate cameras. Our method enables clearer visualization of each process individually and reveals the correspondence between the two imaging sources, effectively integrating their information.
Specifically, we consider a dynamic scene with three rotating figurines, each spinning at a different angular speed. The rotation angles define the latent parameters governing the scene (Lederman & Talmon, 2018). Two cameras capture this scene simultancously: both record the shared bulldog figurine, while each also captures a unique, camera-specific figurine. At each time point, the two corresponding image frames- one from each camera- are concatenated horizontally to form single, wider image. This sequence of concatenated images constitutes the dataset used in our analysis, comprising N = 5000 grayscale images with D- = 9600 pixels each, as illustrated in Figure 5(a). As a result, each individual camera view depends on two latent parameters, while the stacked dataset as a whole is governed by all three.
In (Lederman & Talmon, 2018) and similarly in (Lindenbaum et al., 2015), the views were treated separately and then aligned to extract the shared component. In contrast, our method operates directly on the concatenated dataset, allowing
16

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High--Dimensioal Data
1.0
ISNE
FP (Ours)
IC-PML
0.8
LDLE
Multi- Ualti-ISNE
All Features
Error
0.6
FP Features (Ours)
0.4
0.2
K-Nearest Neighbors
(a) Illustration of the data generating process.
(b) Quantative comparison.
ISNE Embedding Based All Pixels Buildog Angle
Yoda Angle
Bunny Angle
Embedding Portition (Gray) Buildog Angle <
Partition (Yellow) Color: Yoda Angle
Partition (Pink) Bunny Angle V
(c) The three extracted partitions using approach.
(d) ISNE embeddings.
Figure 5. Partitioning and embedding data from two concatenated views of rotating figurines. The dataset consists of N = 5000 grayscale images, each with D 9600 pixels, formed by horizontally concatenating synchronized vidco frames from two different viewing angles (illustrated in Figure 5(a)). (a) Illustration of the data acquisition sctup. At cach time point, two cameras simultancously capture the scene, each observing two out three rotating figurines (Yoda, Bulldog, and Bunny), which are rotating at distinct angular speeds. (b) Quantitative comparison of embeddings produced various algorithmss, evaluated using K-nearest neighbor latent angles of the figurines. Our method yields the lowest error, indicating that the extracted partitions best reflect the underlying structure. Further evaluation details provided in Appendix D. (c) The three feature partitions identified by our method (indicated by three different colors). (d) Top row: iSNE embeddings using all pixels, with data points colored hy the rotation angle of the Yoda (left), Bulldog (center), and Bunny (right) figurines. Bottom row: iSNE embeddings based on each extracted partition, colored respectively by the angle of the figurine best captured by that partition (left: Yoda, center: Bulldog, right: Bunny), as shown in Figure 5(c).
against the known
17

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Data
Diffusion Maps Embedding Based on All Pixels
UMAP Embeddling Based on Pixels
Color: Yoda Angle
Bulldeg Angle
Bunny Angle
Color: Yoda Ancle
Bulldog Angle
Bunny Angle
Diffusion Maps Embedding Based Partition [Gray] Bulldoog Angle
UMAP Embedding Based Partition (Gray) Dulldeg Angle
Partition (Yellow) Color: Yoda Angle
Partition 3 (Pink) Bunny Angle
Partition 1 (Yellow) Color: Yoda Angle
Partition 3 (Pink) Bunny Angle
(a)
(h)
Figure 6. Embeddings of two concatenated views of rotating figurines. (a) Top row: Diffusion Maps embedding based all pixels colored by the angle of the Yoda (top left), Bulldog (top middle), and Bunny (top right) figurines. Bottom row: tSNE embeddings based on the first (bottom left), second (bottom middle), and third extracted partitions (bottom right) shown in Figure 5(c), with data points colored by the angles of the Yoda, Bulldog, and Bunny figurine, respectively. (h) Embeddings using UMAP analogous to (a).
us to recover the substructure associated with each figurine-inchune those whose visual footprint spans both camera views. This leads to better visual separation of the underlying processes and reveals the correspondence between the two measurement sources.
We apply our approach to the stacked images and extract K pixel partitions. Figure 5(d), we compare the tSNE embedding based on all the pixels with the embedding based on each pixel partition. While the embedding based on all pixels reflects only the Bunny figurine's angle, the partition-based embeddings successfully capture the rotational structure originating from all the figurines, with each embedding corresponding to specifie figurine. In Figures 6(a) and 6(b), further compare the embeddings obtained using UMAP and Diffusion Maps to validate the observed structures.
In Figure 5(b), we quantitatively compare the iSNE embeddings generated from our pixel partitions with those produced by alternative techniques, similarly to the comparison in Section 5.2. The error measure used here differs slightly, as the ground truth latent variables are continuous rotation angles of three figurines, rather than discrete clusters. Hence, to compute an error measure for a given embedding of the dataset, do the following. For each data point and for each one of the three rotation angles, we find the k nearest neighbors of point and the nearest angles of angle and compute the relative set difference between the two groups. Specifically, the score is defined as the number of neighbors in the angle-based set that are not present in the embedding based set, divided by k. This provides three scores of angle inconsistencies for each point (corresponding to the angles). Following the same procedure used in Section 5.2, we then average these scores across all data points, producing three error measures that quantify the inconsistency of the embedding with respect to the three figurines' angles. For methods that provide a single embedding the data, we average these three scores, quantifying how much this embedding consistent with all the latent processes. For methods that produce three embeddings, we expect each embedding to be consistent with only one of the latent processes. Therefore, in such cases, assign each embedding only one of its three scores (without repetition) such that the average of the assigned scores is minimized for the three embeddings.
All methods were applied a consistent manner with the setup described Section 5.2, with necessary adjustments to support the comparison across multiple embeddings when applicable. In particular, for algorithms capable of producing multiple embeddings, we generated three-one for each latent process. The results demonstrate that our method significantly outperforms the alternatives in aligning with the underlying rotational structure of the data, highlighting its effectiveness in disentangling independent sources of variation.
We further evaluate our approach by comparing it to traditional clustering methods when applied to the feature space instead of the sample space. Specifically, we extract K = 3 partitions using k-means and spectral clustering, treating the values of each feature across all images as a sample point in N We also apply these algorithms with K = to provide a more flexible setting that may better capture the structure present in the data. The resulting partitions, shown in Figure 7, highlight that both k-means and spectral clustering fail isolate each figurine into a distinct partition, whereas our approach
18

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hligh-Dimensionie Data
(a) An image from the dataset
(b) K-means (K=3)
(c) K-means (K=4)
(d) Spectral Clustering(K=3,100 (00mmmm.00331100mmigee.3))
(e) Spectral Clustering KK=,,00-n,eiigs-/
Figure 7. Pixel partitions generated using k-means and spectral clustering by clustering the pixel data while treating the samples coordinates (i.e., applied the transposed data matrix). Each color indicates a different partition. Here, denotes the number of clusters used, 10-nn refers to the use of 10-nearest neighbors graph, and "eigs" indicates the number of eigenvectors used in spectral clustering.
successfully does so, illustrated in Figure 5(c).
To quantitatively assess how well each approach partitions the pixels and captures the underlying structure of the data, evaluate the correspondence between each extracted pixel partition and the true rotation angles of the figurines- the latent variables governing the data. To this end, we define an accuracy measure as follows. For given partition and figurine, we compute the relative overlap between two sets 50-nearest neighbors for each image: one based on the true figurine angle and the other based on the pixel values restricted to the partition. The relative intersection score, defined as the size their intersection divided by 50, reflects how strongly the latent parameter (rotation angle) is expressed in the partition's 's feature space. Since the figurines rotate independently, an ideal partitioning should align with exactly figurine's angle. Thus, for each approach, match each figurine the partition with the highest relative intersection score and report the average correspondence across all three figurines. Furthermore, above, and report its average across all three figurines. We repeat this evaluation using 30-nearest neighbors to provide additional insights into the consistency of the results.
compute the standard deviation of the relative intersection score
The resulting mean overlap score are shown Table 2, reflecting the accuracy of each approach in partitioning the pixels into the true subsets associated with each figurine. As evident from the results, our approach substantially outperforms the clustering methods and more effectively isolates the latent factors of variation.
Thus, to conclude, our approach outperforms both clustering and embedding- based methods in capturing the underlying structure of the data. By effectively isolating the latent factors of variation, it provides more faithful decomposition of the observed measurements, demonstrating clear advantages over traditional techniques.
Implementation details. To generate the embedding of the tSNE embedding based on all the features in Figure 5(d) we used perplexity of 40 with 100 simulations. The visualizations using the tSNE algorithm of the data based on each partition
19

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Highh-Dimensional Data
Agreement of
Agreement of
Method
30-nearest neighbors (std)
50-nearest neighbors (std)
All features
8.21 (4.91)
11.74 (4.75)
K- means (K=3)
18.49 (9.74)
25.93 (10.61")
K-means (K=4)
18.23 (9.11)
25.42 (10.31)
Spectral Clustering (nn=10,K=3,, eigs=3)
18.28 (8.4)
24.72 (8.82)
Spectral Clustering (mn=10.K=4.cigs) 4)
18.85 (8.71)
25.49 (9.19)
Spectral Clustering (nn=30,K=3, eigs=3)
18.12 (8.5)
24.47 (8.97)
Spectral Clustering (mn=33.K=4,cigs=44
18.19 (8.5)
24.53 (8,98)
Spectral Clustering (mn==10.K-3.eig==5)
18.04 (8.5)
24.41 (8.98)
Spectral Clustering (on=10.K=4.eig==5)
18.63 (8.76)
25.25 (9.26)
Spectral Clustering (mn=10.K-3..iis=-0)
17.51 (7.94)
23.8 (8.22)
Spectral Clustering (nn=30.K=44.cie=-0)
18.94 (10.35)
25.49 (11.51)
FP (Ours)
75.93 (12.22)
85.15 (8.59)
Table 2. Quantitative comparison of different pixel partitions produced by various clustering algorithms, evaluated using k-nearest neighbor against the known latent angles of the figurines. Our approach yields the lowest error, indicating that the extracted partitions best reflect the underlying structure. The "All Features" baseline refers to using all pixels to compute the k-nearest neighbors without applying any partitioning. Here, K indicates the amount clusters used within each method, "nn" indicates the amount of nearest neighbors, and "cig" indicates the amount eigenvectors used. For the Feature Partioning method partitioned the pixels into 3 partitions. Further evaluation details are provided in Appendix D.
uses perplexity of 110. The high perplexity can be attributed to known issue with tSNE, where it sometimes distorts circular embeddings, resulting in discontinuities. A common solution to this problem is to increase the perplexity of the embedding.
The Diffusion Maps embeddings, shown in Figure 6(a), were generated using a bandwidth parameter that the maximal squared Euclidean distance among each data point and its corresponding 10-nearest neighbor. Furthermore, we used normalization factor of a 1. Finally, the UMAP embeddings based on our extracted partitions in Figure 6(b) were generated using a local neighborhood parameter (n_neighbors) of 80 due to the 1-dimensional structure of the embedding. This is due to the same issue as discussed above for iSNE. The UMAP embedding based on all the features was constructed with its default parameter 15.
Details of Quantitative Comparison with Embedding- -aaed Methods. The parameters used for each algorithm are identical the ones used in Section 5.2, with the exception that we generated 3 embeddings for any algorithm that allowed it, for LDLE we used the Mmin parameters of and 10, and for the tSNE of our extracted partitions used perplexity of 10. We note that our approach was applied with entropy constraints that correspond to perplexity of 10.
Details of Quantitative Comparison with Clustering Methods. The parameters used for k-means and spectral clustering followed the default settings in scikit---- filk-iteeear unless stated otherwise.
E. Numerical Comparison of Empirical and Analytical Loss Landscapes
In Figure 8(a), we compare the empirical loss landscape of (16) with its analytical counterpart derived in (17), for the case K = 2. The dataset consists of N = 1000 samples drawn uniformly from three latent manifolds, M2,M2, M3 C R where each manifold forms a unit circle and M3 serves as the shared component between partitions. The observed feature dimensions are D1 = 2500 and D3 = 7500. As predicted by Theorem 4.3, the minima of the loss function occur near the ground truth partitioning solutions (i.e., P1 = 1,P2 = 0 or vice versa). In Figure 8(b), we show the empirical landscape of the original loss function defined in Problem 3.3 under the same data configuration. The observed landscape closely resembles that of the simplified objective studied in Section 4, further supporting the validity of the analytical approximation.
20

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hiigh-Dimensional Data
Objective Landscape for the Analysis Section
Objective Landscape for the Feature Partitioning Problem (Mean over 100 Simulations)
Analytical Landscape
Empirical Landscape
(Mean over 100 Simulations)
0.60
0.2
0.2
13.0
12.5
0.4
12.0
0.6
0.40
0.8
0.35
11.5
0.30
0.2
0.4
0.6
0.8
0.2 0.4
0.6
0.8
0.4
0.6
P2
Pz
(a)
(b)
Figure 8. An experiment based on Section for K = 2 with with e 0.2. (a) The analytical loss landscape of Problem 4.1 presented in (17) (Left) and the mean empirical loss defined in (16) (Right). For the empirical case, the pL, Ps (0, 1) indicate the proportion of features out of the two feature subsets used by ( while (2) taking the remainder. The color represents the mean value over 100 simulations, based the affinity matrices defined in Corollary 4.2. (b) We consider similar empirical loss based Problem 3.3 (min ( x
k== ( ). )), where the affinity matrices are as defined in (9). The perplexity parameter was set 20. Additional details be found in Appendix E.
G((W(A) (k) [ (
F. Experimental Details and Additional Results
F.I Details for Section 5.1
In this experiment, we define two sets, v C R.O. The two datasets are defined based on a 2-dimensional ellipse defined by
A = {88 (6) sin(Ø), 6 sin sin( cos(
θ E [0, 2m,] E [0,T]}
(27)
and R, S R 3x3 be orthogonal matrices. We now define the sets by
{
Ra
a.bEA
(28)
Sb
Ra
a,beA 0(a) ((a)=
y
(29)
Sb
where ((a) denotes the polar angle 0 corresponding to the data point in the parametrization of A in (27).
The set y corresponds to the independent case discussed in Section 5.1, where as the first three and last three coordinates are independent of each other. Additionally, y represents the partially-dependent case, in which the first and last three coordinates are partially coupled through a shared polar angle. In both cases, the samples used by ........ N y and y...... y y- were drawn independently and uniformly from their respective sets.
experiment- denoted
This experiment evaluates the ability of our approach and several baseline algorithms to partition the coordinates into the true feature subsets defining the data namely, the first three coordinates and the last three. The comparison includes Spectral Co-Clustering (Dhillon, 2001). Spectral Bi-Clustering (Kluger et al., 2003), k-means (Lloyd, 1982) and spectral clustering (Ng et al., 2001). We evaluated Spectral Co-Clustering and Bi-Clustering using their feature clustering. Additionally, we applied k-means and spectral clustering on the features, treating samples as coordinates (i.e., applied on the transposed data), and clustering them into K groups. Additionally, for spectral clustering, we used two embedding dimensions. The output of each of the clustering algorithms will be considered as a pair of binary indicator vectors w .((2) 13
Specifically, the vector (2) e {0, 1] takes the value for all coordinates assigned to the first cluster and 0 otherwise. The complementary vector @ (2) is defined analogously, indicating membership in the second cluster.
Finally, we define the error measure used to quantify the discrepancy between the estimated partitions (1)) ..(2) (2) E [0.1] and the true partitions (1), (2) {0, 13. As discussed above, the true partitions are given by (1) (1, 11,1,1,0,0,0),
21

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimennioonl Data
UMAP Embeediig based on Genes
Genes
Genes
Diffusion Maps Embedding based on Partition
Genes
Partition
LD
UD
DC
DC
G1
GZM
-000
(a)
(b)
Diffusion Maps Embedding based
UMAP Embodding based on
All Genes
Partition 1 Genes
Partition 2 Genes
All Genes
Partition Genes
Partition 2,Genes
DC
DC
GL
G2M
G2M
(c)
(d)
Figure 9. Additional embeddings of the ScRNA-seq data from Section 5.2, highlighting the advantages of our approach to discover distinet salient cellular processes. Plots (a) and (c) show the UMAP embeddings of the data in two and three dimensions, respectively, using either all genes or only the genes from partitions! and 2. Similarly, plots (b) and (d) present the corresponding Diffusion Maps embeddings. Within each plot, the top includes the cells' embeddiins colored by their cell type, with partition 1 revealing the LD/UD to DC developmental trajectory. At the bottom, the cells are colored by the cell type, with partition 2 revealing the cycling progression.
with (2) being the complimentary vector. The error is defined
d( (1 K (w (K)) ki))
min (|) (1)) kE(1.2)
(30)
where ||a]]| = 2d=1 |aal denotes the L1 norm. Only (1) considered, as (2) is its complementary partition. This error can be interpreted as normalizedd Jaccard distance between the true feature partition and the estimated one, up to permutation of the ordering of partitions.
E.2. Details and Additional Results for Section 5.2
This section provides additional information and extended results related Section 5.2. We begin by describing the preprocessing applied to the dataset, followed by additional visualizations using the extracted feature partitions. We then repeat the experiment using larger gene set and related dataset to further demonstrate the applicability of our method. Finally, we provide details about the quantitative evaluation done in the main text.
Dataset Preprocessing. Section 5.2, we applied our approach to the dataset used in (Qu et al., 2024), specifically the wild-type cells within the E14.5 WL. experiment. The data included a count data matrix comprised of 5, 572 cells along
22

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Bigeh-Dimnnional Data
tSNE Embedding based Partition 1 Genes
All Genes
Partition 2 Genes
LD
up
DC
G1
G2M
Figure Embeddings obtained by repeating the experiment Section 5.2 using 10000 genes (instead of 5000 in Section 5.2). The embeddings in the upper row colored according the cell type, while the bottom row (containing the same embeddings) is colored according to the cell cycle state. The embedding based on the genes and the embedding from partition 2 reflect the cell type development, while the embedding based partition uniquely reflects the cell cycle development. We can see that despite the additional variation due to the extra genes, the substructures remains clearly visible.
with their 32, 285 gene expressions. We employed the normalization scheme from the Seurat package, where the gene counts in each cell were divided by the total number of genes within that cell and then scaled by 10, 000. Each entry was subsequently log-normalized using the transformation log(1 + z). We then retained the 5, 000 most highly variable genes. Finally, we used the z-score transformation each gene across the samples and reduced the rank of the data matrix to 50
by truncating the singular value decomposition (SVD). As for our approach, we applied Algorithm on the data using perplexity parameter of 40 and 100 simulations.
For comparison, Qu et al. (2024) used only the top 2, 000 highly variable genes and retained the top 30 principal components, which corresponds to keeping the leading 30 components in the SVD. Thus, our configuration involves a larger set of genes and higher-rank representation, retaining more variability the data.
We evaluated the alignment between partition 2 and cell-cycle activity using Seurat's updated G2M and S phase gene sets (cc.genes.updatl 2201 in Seurat 5.3.0) (Tirosh et al., 2016), which are commonly used in single-cell analysis. Since these lists use human gene names, we mapped them to mouse counterparts with gprofiler2 (v0.2.3), yielding 95 genes. Then, we removed the genes that were filtered during the data preprocessing stage, resulting in 86 remaining genes. All 86 genes were assigned to partition 2. indicating that the cell-cycle signal governs this partition.
The effectiveness of our feature partitioning further demonstrated through additional embeddings of the dataset, computed using all genes as well as each extracted partition; see Figure 9, As in Figure 3, the embedding based all genes reveals only the cell type, while each partition reveals only of the biological processes: cell rype (by partition 1) and cell cycle (by partition 2). It is evident that the partitioning of features has vital effect on visualization techniques in general, and is not specific to ISNE.
Additional Results.
We next repeat the original experiment in a more challenging setting using 10, 000 of the most variable genes to show robustness of our approach. By increasing the number of genes, we allow noisy features into our dataset, making the partition task more complex. We applied our approach again with К 2, and Figure 10 we compare the tSNE embedding based on all genes, with the embeddings based on each of the extracted partitions. Evidently, the two partitions still extract the two underlying structures that correspond the cell type (by partition and cell cycle (by partition 1). Furthermore, we validated these partitions using known gene markers for each biological process, as described in the final paragraph of Section 5.2. Specifically, the gene markers associated with cell type were found in partition 2. For the cell-cycle genes, we used Seurat's 's updated G2M and S phase gene sets, originally comprising 95 genes. After removing the genes that were filtered during the data's 's preprocessing stage, only 93 genes remained, and they were all assigned to partition This indicates that the genes were partitioned effectively according to the biological underlying processes.
23

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dimensionnnnin Data
tSNE Embedding based on Partition Genes
All Genes
Partition 2 Genes
LD
UD
DC
G1
S
G2M
tSNE Embedding based on Partition 1 Genes
All Genes
Partition 2 Genes
LD
UD
DC
G1
S
G2M
Figure 11. A similar experiment to the one done in Section 5.2 on different dataset. Plot (a) shows the embedding of N 5598 cells characterized by their 5000 gene values, while plot (b) presents the corresponding embedding obtained using D 10000 genes. The upper row within each plot indicates each cell's type, while the bottom row shows each cell's cell cycle state. As shown, the embeddings based on genes and partition genes are inductive to cell type development (top), while the embedding based on partition genes reflects the cell cycle development (bottom).
We repeat the experiment on a similar dataset to further validate our results on data with similar characteristics. Specifically, we consider the wild-type cells within the E14.5 SMOM experiment (Qu et al., 2024) that consists count data matrix with 5, 598 cells along with their 32, 286 genes expressions. We apply the same preprocessing pipeline as in the previous experiment, including the selection of highly variable genes. As before, evaluate two configurations: using the top 5, 000 most variable genes and another using the top 10, 000.
In Figure 11, we show the results for both configurations. We compare the iSNE embeddings based on all the genes with the embeddings based on each extracted partition. As shown in Figure 11, the embedding based on all the genes reveals only the structure related to the cell type development, while obscuring the cell-cycle phase. On the other hand, the embeddings from our two partitions reveal both the cell-cycle phase and the cell type development (in partition and respectively).
24

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimenniooal Data
Furthermore, we validated these partitions using known gene markers for each biological process, described in the final paragraph of Section 5.2. Specifically,, the gene markers associated with cell type were found in partition 2. For the cell-cycle genes, we used Seurat's updated G2M and S phase gene sets, originally comprising 95 genes. After removing the genes that were filtered during the data's preprocessing stage, only 63 out of the 95 genes remained in the 5, 000-gene dataset and 81 out of the 95 in the 10, 000-gene dataset. In both cases, all these genes were assigned to partition 1. This indicates that the genes were partitioned effectively according to the biological underlying processes.
Quantitative Comparison. The quantitative comparison shown in Figure 3(b) evaluates how well the embeddings generated based on our extracted partitions reveal the two underlying processes of the data compared to other methods. To define error measure for given embedding of the dataset, two types of labels (cell phase and type), we find the k nearest neighbors of point and compute the proportion of nearest neighbors whose label differs from the label of point This provides two scores (of label inconsistencies) for each point, corresponding to the two processes. We then average these scores across all data points, producing two error measures: one quantifying the inconsistency of the embedding with respect to the cell phase and the other with the cell type. For methods that provide single embedding of the data, we average these two scores, quantifying how much this embedding consistent with both latent processes. For methods that produce two embeddings, we expect each embedding to be consistent with only one of the latent processes. Therefore, in such cases, assign to each embedding only of its two scores (without repetition) such that the average of the assigned scores is minimized for the two embeddings.
proceed follows. For each point (cell) and each of the
Next, we describe the parameters used by the different embedding algorithms in the quantitative comparison. It is important to note that the error measured for IC-PML, Multi-tSNe and LDLE for each specific K -earrestt neighbor corresponds to the smallest error observed across a wide range of hyperparameter values. The specific hyperparameter settings explored are detailed below:
IC-PMI. (960 parameter configurations):
Number of manifolds: 2
Total eigenvectors: 50
Number of eigenvectors used from each manifold: 21,2,3,4,55 4,
Epsilon parameters: the maximal distance between each point and k-th nearest neighbor, where the considered
k included 5, 10, 20, 40.
Similarity criterion coefficient: [0.01, 0.03, 0.05, 0.1,
Figenvalue criterion coefficient: [0.01, 0.03, 0.05, 0.3,0,,,
L.D.E (32 parameter configurations):
Embedding dimensions:2 and 3.
Mmin: 10 and 20.
k_tune: 5, 10, 20 and 40
torn: We considered the torn and non-torn data embedding options.
Multi-tSNE (8 parameter configurations):
Number of maps:
Embedding dimension: 2 and 3.
Perplexity: 10, 20 and 40.
tSNE based on all features (8 parameter configurations):
Embedding dimension: 2 and 3. Perplexity: 5, 10, 20 and 40.
Feature Partition (Ours):
Perplexity: 40
Simulations: 100
tSNE based on the Feature Partition (Ours):
25

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Bigh--Dimensional Data
Perplexity for Feature Partition: 40
Simulations for Feature Partition: 100
Perplexity for tSNE: 40
Embedding dimension: 3
26

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of
Data
F.3. Data Preparation and Comparative Visualizations for Section 5.3
In Section 5.3, we applied our approach the dataset used in (Droin et al., 2021). The data included count data matrix comprised of 6889 cells along with their 14812 gene expressions. We employed the normalization scheme from the Seurat package, where the gene counts in each cells were divided by the total number of genes within that cell and then scaled by 10000. Each entry was subsequently log-norman oognoomalized using the transformation log(1 +2). We then retained 2000 of the most highly variable genes. Finally, we used the z-score transformation across the samples and applied principal components analysis (PCA) to reduce the data to dimension 20. As for our method, we applied Algorithm using a perplexity of 40 and 100 simulations. All ISNE embeddings used a perplexity of 40.
Cell Displayed Across Layers: All Cells in Blue, Specific Layer Overlaid in Orange
Layer 1
Layer
Layer 5 tSNE Embedding Based on All Features
Layer 3 Layer
Layer 6
Layer 7
Layer
20
20
D0
-00
-30
-50
-M0
tSNE Embedding Based Partition
0
50
-50
-50
-5
-50
-50
-50
50
-50
-50
90
tSNE Embedding Based on Partition
30
30
30
30
-50
50
50
50
50
50
5
:0
50
50
5
50
50
50
30
50
Cells Colored by Circadian Clock Phase
tSNE Embedding Based on
All Features
Partition 1
Partition 2
50
ZTO
ZT6
ZT12
ZT18
-50
50
50
(b)
Figure 12. iSNE embeddings generated using all the features and using the features from our proposed partitioning. applied to the liver dataset described in Appendix F.3. Embedded data points (blue) overlaid with the labels of specific liver layers (orange). (b) Embedded data points are colored according to their circadian clock phase. Our method effectively disentangles the two underlying factors: partition captures the spatial liver layer structure while partition captures the circadian phase. contrast, the tSNE embodding using all features reflects a complex mixture of both variables, making it difficult to interpret the embedding.
27

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- DiahhsDDinniin Data
Objective Value as a Function of Partition Count
10a
Minimized Objective Value
100
K: Amount of Partitions
Figure 13. The minimal objective value achieved by our algorithm (defined in (8)), normalized by the number of samples N, as function of the number of partitions K. Results are shown for the dataset of three rotating figurines used in Appendix D.
G. Choosing the Number of Partitions (K) and Validating the Usefulness of Our Partitioning
The selection of the number of partitions (K) is a practical consideration that directly affects the outcome of our algorithm and therefore the visualizations generated based on A sub-optimal choice of K can result in visualizations that are either overly complex or redundant. In this section, we discuss how determine K and diseuss the implications of selecting a sub-optimal number of partitions. Finally, propose procedure to verify whether the data is indeed composed of subsets of features that are partially dependent as our approach assumes.
Determine K for K 2 2. In order to determine K we propose to inspect the behavior of the smoothness score from our approach, defined in (8), as a function of the number of partitions K. As long as K increases but remains lower than the true number of partitions, we expect to see a rapid decay of the score. Then, when K reaches the true number of partitions, we expect to see an 'elbow", after which the score saturates or decays very slowly. This phenomenon reminiscent of similar situations, such as manually selecting the number of clusters in k-means or the number of components in PCA. We demonstrate this behavior of the smoothness score in Figure 13.
Next, we discuss the expected impact of over sele-sele or under under-selecting selecting K on the resulting representation and embedding. If the number of partitions is lower than the number of true partitions in the data, we expect the partitions to separate the features into super-groups that correspond to the most distinct geometric structures, even some of these groups could be further subdivided. In this case, each group of features describes a geometry that is simpler than that of the original data, i.e., it has a lower intrinsic dimension. Hence, the outcome of our procedure in this case still improves the ability to embed and visualize the data in a low-dimensional space, albeit sub-optimally where the embedding dimension may need to be higher than it would be if the optimal choice of K was used.
If the number of partitions is slightly larger than the true number of partitions in the data, we expect that one or more of the true partitions will be arbitrarily subdivided. This will introduce redundancy into the representation, where some feature subsets will exhibit similar geometric structures. The user should take into account this possibility and inspect the resulting embeddings for potential redundancy. Nonetheless, the partitioning is still beneficial in this case, since the data for each partition can be easily embedded and visualized in a low-dimensional space. If the number of partitions is grossly overestimated, then in addition to redundancy, some of the feature subsets may not reliably represent the underlying geometry of any of the true feature subsets.
Determine Whether K = 1. When the data cannot be partitioned into features with simpler structures, we expect that applying our algorithm to partition the features into two or more groups will result in partitions with similar or nearly identical underlying structures. Consequently, the graphs that correspond to the partitions will also exhibit similar characteristics, leading to embeddings (such as (SNE) that closely resemble each other.
28

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimennsonal Data
To determine if the features can be partitioned into meaningful subsets, we propose a type of permutation test. Specifically, propose to compare the smoothness score produced by method from the original data the analogous score obtained from manipulated versions of the data. The manipulated versions are obtained by applying random orthogonal transformation to the features, in which case the data does not satisfy our underlying assumption by design. The different steps of this procedure and their justification are detailed below:
1. Apply our procedure with K = 2 to the given data matrix and store the associated score, defined in (8).
2. Generate multiple modified versions of the dataset by applying random orthogonal transformation to the features of the data. Each orthogonal transformation randomly mixes all the features in the dataset. If distinct feature partitions existed in the original data, they will be completely mixed after the transformation. Hence, our underlying assumption does not hold for these manipulated datasets.
3. Apply our procedure with K = 2 to each transformed dataset and store the associated scores, defined in (8).
4. Compare the score from step 1 to the distribution of the scores from step 3. If the score from step 1 is smaller than chosen percentile of the scores from step 3 (e.g.. 0.01), we conclude that the original data contains feature partitions with significantly distinct structures, suggesting that our assumption holds, at least to some extent.
H. Experiment on the COIL-20 Dataset
We conducted an additional experiment using subset of the COIL-20 dataset (Nene et al., 1996), consisting of 128 x 128 grayscale images of three distinct but visually similar captured varying azimuths. While this dataset may not explicitly satisfy our approach's 's theoretical assumptions, it provides an interesting test case for our approach. For this experiment, we used all images from the car objects 2, 5, 18, which resemble one another, resulting in 216 images in total. The images were flattened to vectors and the resulting dataset was approximated using its 20 leading SVD components to reduce its variability.
We applied our algorithm with K 2 partitions and two different perplexity parameters: 10 and 20. The resulting (SNE visualizations can be seen in Figure 14. Evidently, the standard tSNE visualization that use all pixels (left) reveals closed loop structure corresponding to the object's azimuth. Notably, partition (middle) produces more coherent representation of the azimuth, demonstrating also enhanced stability across different perplexity values. Interestingly, partition 2 (right) effectively separates the images based on car identity, suggesting our method naturally discovered semantically meaningful features. The actual pixel partitions are shown in Figure 14(c). Specifically, partition 1 identified the outer pixels that typically capture the front and back of the car- far-features that correspond more closely to the azimuth of the object rather to its identity, reflected in Figures 14(a) and 14(b). In contrast, partition 2 focused on the rooftop region, which corresponds more directly to the identity of each specific car object.
29

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Hiigh-Dimeniionl Data
tSNE Embedding Based on
All Pixels
Partition (Yellow)
Partition 2 (Blue)
60
40
Object Type
20
20
Object
0-
Object
C
Object
-20
-20
-20
Azimuth Colored by
-40-
-50
50
-50
70
60
40
50
Object azimuth
20
20
-40
40
(a) tSNE embeddings with perplexity parameter of 10
tSNE Embedding Based on Partition 1 (Yellow)
All Pixels
Partition 2 (Blue)
g
Object Type
10
20
0
Object Object Object 18
g
0
-20
-10
Azimuth Colored by
-20
-20
-25
25
-20
20
-20
20
70
60
20
50
20
6
40
30
20
-20
10
-40
20
(b) ISNE embeddings with perplexity parameter 20
Extracted Feature Partitions Overlaid Images
(c) Extracted partitions overlaid in blue and yellow three sample images.
Figure 14. The experiment detailed in Appendix H. The dataset includes N = 216 gray-scale images with D = 16, 384 pixels from COIL-20. Each image contains single rotated object, the considered objects are three types of cars. (a) ISNE embedding the data with a perplexity parameter of 10, (b) iSNE embedding of the data with perplexity parameter of 20. (c) Three sample images from the dataset, overlaid with the partitions extracted by Algorithm shown in yellow (partition 1) and blue (partition 2).
30

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Sigh--iimeniooal Data
I. Proofs
Proofs overview.
This section is organized into three main parts: Appendix I.1 contains the proofs of the results in Section 3, Appendix I.2 presents the proofs of the results in Section 4, and Appendix 1.3 includes the proofs of the results in Appendix C.
Below is brief outline of the results and proof' presented in Appendix I.I:
1. Lemma I.1. This is an auxiliary lemma used in Proposition 3.1 and Lemma 1.3 that characterizes the entropy function of a discrete distribution. Specifically, it considers a normalized exponential distribution that is based on the pairwise distances within the data.
2. The proof of Proposition 3.1. The proof begins by showing that the problem is convex. Then, it derives an optimal solution to the optimization problem under some assumptions of the data by using the Maauush-Khn-TTeee (KKT) conditions for convex optimization problems using Lemma I.I. Finally, we derive an optimal solution that admits the same form as the previous one when the assumptions do not hold.
3. Lemma I.2. This is an auxiliary lemma used in Proposition 3.2 that approximates specific integrals over a manifold in terms of the manifold's properties and density. The lemma uses results from (Singer, 2006).
4. The proof of Proposition 3.2. The proof begins by asymptotically approximating the function using results from (Hein et al., 2005). Then, it derives its expression using Lemma 1.2 in terms of the manifold's characteristics and density. Finally, a further simplification of the expression done by referring to results from (Osher et al., 2017).
5. Lemma I.3. This is an auxiliary lemma used Proposition 3.4 that characterizes the optimal graphs a Problem 3.3 with fixed partitions. The proof begins by showing that the problem is convex. Then, it derives an optimal solution to the optimization problem under some assumptions of the data by using the Karush-Kuhn-Tuue (KKT) conditions for convex optimization problems using Lemma I.1. Finally, we derive an optimal solution that admits the same form as the previous one when the assumptions do not hold.
6. Lemma L.4. This is an auxiliary lemma used in Proposition 3.4 that characterizes the optimal partitions in Problem 3.3 with fixed graphs.
7. The proof of Proposition 3.4. The proof divides the problem into two sub-problems, fixing either the feature partitions their associated graphs in each case. Then it combines the results from Lemmas I.3 and 1.4 to fully characterize the problem's 's optimal solutions.
Similarly, below is an outline of the results and proofs presented in Appendix I.2:
1. The proof of Corollary 4.2. The proof begins by proving that the optimization problem is convex. Then, it derives an optimal solution to the optimization problem under some assumptions of the data by using the Kainsh-KuhnTTiie (KKT) conditions for convex optimization problems using Lemma I.1. Finally, we derive an optimal solution that admits the same form as the previous one when the assumptions do not hold.
2. Lemma 1.5. This an auxiliary lemma used in Lemma 1.6 and Lemma 1.7 to generate an upper bound for a given event by separating into multiple events.
3. Lemma I.6. This is an auxiliary lemma used Theorem 4.3 that characterizes a specific sum in terms of the data setup parameters and partition parameters defined in Section 4.
4. Lemma 1.7. This is an auxiliary lemma used in Theorem 4.3 that characterizes specific sum via an integral, in terms of the data setup parameters and partition parameters as defined in Section
5. Lemma L88 This is an auxiliary lemma used in Lemma 1.9 that approximates specific integrals over a manifold in terms of the manifold's properties and density and some predefined parameters. Its proof uses results from Lemma 1.2.
6. Lemma 1.9. This an auxiliary lemma used in Theorem 4.3 that approximates specific integrals over a manifold in terms of the manifold's 's properties, density and some predefined parameters. Each the integrals under consideration includes a nested integral, with the inner integral being addressed in Lemma 1.8.
31

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimennional Data
7. The proof of Theorem 4.3. The proof begins by solving the minimization problem over the graph parameters derived in Corollary 4.2. It then asymptotically approximates the solution the dimension and number of samples tends to infinity, utilizing Lemmas L6 and 1.7. Next, it approximates this asymptotic value by applying Lemma 1.9 to express it in terms of the manifold's properties, density, and partition parameters.
8. Lemma I.10. This auxiliary lemma, used in Theorem 4.4, considers the case of two partitions. It demonstrates that the analytical form derived in Theorem 4.3 is minimized when the partitioning is close to the true feature partitioning under a constraint on the possible partitioning solutions.
9. The proof of Theorem 4.4. The proof builds on Lemma I.10 by considering a sequence of problems and demonstrates that the problem is minimized when the true partitioning solution is used.
Finally, below we outline the results and proof' presented in Appendix I.3:
1. Lemma L.1. This is an auxiliary lemma used in Proposition C.2 that characterizes the optimal graphs in a Problem C.I with fixed partitions. The proof begins by showing that the problem is convex. Then, derives an optimal solution to the optimization problem under some assumptions of the data by using the Karush-Kuhn- (ubn-Tucker(KKT) conditions for convex optimization problems using Lemma I.1. Finally, we derive an optimal solution that admits the same form as the previous one when the assumptions do not hold.
2. The proof of Proposition C.2. The proof divides the problem into two sub-problems, fixing either the feature partitions or their associated graphs in each case. Then combines the results from Lemma I.3 from Section Appendix I.1 and Lemma 1.1 achieve full characterization of optimal solutions to the problem.
3. The proof of Proposition The.The proof begins by evaluating the objective of Problem C.I under a specific regulariza- tion parameter, using the soft uniform partitioning and its corresponding affinity matrix as defined in Proposition C.2. It then upper bounds this value by the objective achieved by any hard partitioning solution.
4. The proof of Proposition C.4. The proof analyzes the computational complexity of each update rule proposed in Proposition C.2.
5. The proof of Proposition C.5. The proof analyzes the computational complexity of each update rule proposed in Proposition C.2 when the data is given the form of singular value approximation. It starts by rewriting each term as a multiplication of matrices and then derives the computational complexity by considering each multiplication within.
I.1. Proofs of Section 3.1 and Section 3.2
Lemma I.1. Let i E {l....,., N}, and let A...... AN E [0, oo) be some distance function between the i-th element and all the other elements. Define the function f [0, 00) + R by
f(8) = Σ EE
exp(-A,)
cxp(-A,3)
log E []](() exp( -A3)
(31)
JE(1..,,NH/A ElE(
Then is a non-decreasing function and satisfies
lim f(3) - -log(N- 1) and 3-0
lim f(0) = - log(ān)), 8
(32)
where à; = =11 E (1....,, N 1} A, = min. (1...., M)/() A.). Furthermore, any j E exp(-A,})
we ger that
exp(-A,33)
E Lie(I.... N)((1) exp(- - log
(33)
Exe( N)/(() exp( -A,)) iʃA, = āN else
Proof.
We indicate that this proof is not new, and shown here for completeness. Without loss generality the proof will assume = N. Therefore, nn that will be used throughout the proof will be related the i-th element.
32

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Highh-Dimnnsionl Data
The proof will begin by bounding the first derivative of ((3) between zero and some positive constant for all 8 [0, 80), and therefore show that it is non-decreasing. Then, to bound the image of it will derive the value of the boundaries of the domain.
We begin by deriving the bounds of the derivative of f. To do so, we rewrite f by
N-
exp( exp(-A,8)
log exp(-A,,8)
f(8)
(34)
#=1
t=1
N (xp(-An13
exp(
E exp( ()
N-1
exp(-A,88
(og(exp(-A,.1))
(35)
_t exp(
- :
expl 4
N-1
log(
Σ ==1
expl exp(-A.13)
f=1 expl -1,8)
exp(- -A,3)
log(exp( (xxxp(((_)))))
(36)
N-1 expl -,33)
1=1
exp( -133)
N-1
log(
exp(- (A)))
exp( 4.3)
s=1
N-1
expl- -4,3)
N-1
-8
A
-log(
exp( -)))).
(37)
1=1 exp( - -
N-1
The derivative of f is non negative
d3 (8)
(38)
exp( ,
A,
(39)
1== exp( - -)
expl-A (-))))))))))))))) D N-1 exp(- exp( 3 (EA-T exp(-A.3) -A.))
(-a))
A
E exp( 3)2
1=1
exp(- (0,,,,))--A)
Nー1 exp( A)
exp( -A,8)
D
(40)
D1=1 exp(- Ac8)
4
+ DN exp( -,,3)A,
A expl (1,18)
(T
N-1
exp( A,3)
EN' exp( -A,8))
exp( - -,,3)A,
EN exp(- -A,3)
N-1
A
N exp( (-,,,))
=3
A, exp(-A,8)
(41)
NN-I exp( -A,3)
IN-I exp( 2,
==1
N-1
exp( exp(-A,.3 (-)
N-1 N-1
exp(-A,3) expl 4.8))
=3
Σ
Σ A,A.
(42)
1=l exp( - exp(-A,
-1,3)
E N-1 xxp(-),,)))
/=1 ==1
33

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Bighh-Dimensioal Data
2
exp(-A,8)
exp(-A,j)
=8
3
(43)
N-1 -= exp( exp(-A11) -13)
N-1 exp(- - -4,3)
2t=1
exp( -113)
/N-1
Exp(-AAr1) N-1 s=1 exp( - -
3
4
Σ
(44)
W-1
exp( -
-=
20.
(45)
where in (43) we use the variance dccomposition into moments (Var ( E1| x|+] - |||||| || for some random
variable X) and in (44) we use the fact that all the elements are non-negative.
The derivative of f can be bounded from above well will derived below. Based (44),
that
N-1 1 exp( - -1,3)
(s)-
N-1
exp(-A,3)
2
d3 f(0) = B
(46)
1== exp( - -..3)
N-1
N s= exp( - -)
exp( - ,
exp( - - 43
8
43
(47)
1== exp( - -1,3)
1=1 exp( - 1)8)
N-1
exp( - -
8
1=1 ===1 N exp( - - A3
(48)
B4
(49)
JE(L....N-11
Since the derivative of f is nonnegative, its image is bounded by the values it achieves on the boundary of its domain. To find these values, we examine each normalized exponential j E (1,..., N - 1} within f
exp(-BA,)
1
I+ EIE N- 11/(1 exp(( A.)3) E 10.
(50)
EE exp(-BA.)
Its limiting value when 3 tends to zero is
exp( - ,,
lim
lim
(51)
0 Et=1 exp(-A,1)
B 8-20,
N-1 Et=1 exp((A, A,)3)
(52)
-
To derive its value when B + co, we define I = {j E f1...., N -1:: A3 = (I.... A.}. In this limiting case each term converges to
lim exp(-A,13) 80000
(53)
Σ exp( -.13)
lim
(54)
8-000
N- Σ exp((A, - 2.)3)
1
lim Eielain exp((A) A.)3) + Eiglnio exp((A) 2i)3)
(55)
8-300
if E Imin
Imin +(N-1-17)00
(56)
0
else
j Imin
Mmin
(57)
else
as A, A, > for any j & Tiin and E Tmin-
34

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High--iienniionll Data
To connect this result with f. define h : [0, (-o0, 0J by h(a) a log(a) for all E [0, 1]. By composing it with any of the normalized exponentials from above we get that
exp(- A,0)
exp( -,,5)
lim
log N-1
log N
j (I,1.,,,N11
(58)
1=1 exp( - 4,
s=1
exp( 4
exp( -)
1 j E Imin:
lim
log
log
(59)
8-000
Et=l
Σ exp(-A,,3)
Iiin
Imin
where we apply the property that the limit of a product of two functions is the product of each function's limit, given that both exists. Furthermore, when tends to infinity, the limiting value of the term for any j & Imin we converge to
exp( A333
log
(60)
100
1=1 exp(-A,3) Σ exp(-A..)
log N-1 exp((2 - -.)33)
lim
(61)
8-000
E exp((2) (A) -))
N11 ( - -1)13) (Aj -i).
lim
1=1
(62)
8-000
Em1 exp((A) - A,)3)
N 1=1
exp((A) -.)))) (A, A.)
lim
(63)
8-000
N-1 exp((A) 3s)3)
exp( -
lim
(64)
8-000
2x=1 exp(- - -A,99)
N
(65)
where we use the L'Hopital's rule and the result from (53). Now, we can rewrite f as sum of the components defined above by
N-1
exp(- (B
((B)
Σ
1
(66)
exp( exp(-BA.))
==1
1=1
and derive it value at the boundary.
N-1
exp(-3A,
lim f(3)
lim
Σ h
(67)
# 8-0
11=1 exp( - (31,))
N-1
j=l
N
exp(- (322))
=
g-0+ ==
lim h
N- expl (xp())A,)
(68)
1
log
(69)
N-1
exp( -B1,)
lim f(3)
=
lim
Σ
(70)
B
Σ (-p(-BA.))
==1
N
exp( (BB,)
lim h 3-000
(71)
E1=1 exp(-BA)
N-1
=
log
[mmin]
(72)
where we apply the property that the limit of sum of functions is the sum of each function's limit, given that they exists.
Proposition 3.1 The matrix W E [0, 1] N defined in (1) is solution
arg min J(W, (yr...., vN
(5)
W N
35

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Data
subject to the constraints W., o. Σÿ= Wa, = 1 and Σ/= Wo, log Wa, - log(a)) for all i (I,..., NN,, where 61y---; <N E 4 from (1) are the minimum values that satisfy the entropy constraint.
Proof of Proposition 3.1. The proof will demonstrate that the optimal solution can be derived from solving N subproblems, each corresponding to row of the graph solution. We will then use convexity conditions to derive the optimal solution under certain assumptions on the data. Finally, we will show that if these assumptions do not hold, the solution takes a similar form, but with bandwidth parameters approaching zero
We begin by showing that the problem can be solved using N subproblems separately, For each i E {I,...,,N N we define a subproblem related the th row of the graph matrix
arg min ((WWe))=11 ( W Wi x((0.)
(73)
subject to the constraints
=0 O, Σラ Woj and Ej=1 Way log Wa, S - -lo((a), where
N
J. (( =
Σ
Wiylly, - ,,11².
(74)
==1
Based on the next derivation, we can see that the optimal solution should be optimal for each of these sub-problems
min
J(W, (
(75)
W M
N
min W WE
Σ ij=1
W - -y11l
(76)
min
W y; -
(77)
W., Elo.
min
J( 1 (3,1
(78)
where w (k) f.: denotes the i-th row of W (k) and the domain of each minimization problem above contains the constraints that W., = Σmn Way 1 and Σラ= Was log W., S log((a) for all i [I....,NY.
(((
Without loss of generality, we going to find the optimal w......, W that minimize the J, for some i E {1...., N}. Specifically, we assume W., = 0 based on the equality to zero constraint, and omit this constraint. To find the optimal solution, we begin by building on the Karush-Kuhn- Tucker (KKT) Theorem (Corollary 28.3.1 in (Rockafellar, 1970)). We note that this solution will depend on certain conditions; therefore, after this derivation, we will provide an alternative solution that attains a similar form when these conditions are not met.
The theorem assumes that the objective and the inequality constraint is convex and that the equality constraint an affine function. Furthermore, it assumes that there exists solution within the domain that satisfies the inequality constraint in strict manner (Slater's conditions). We begin with the latter assumption, we define valid solution by Wi, 1/(N - 1) for any j # and W., O, as it sums up to ones. The entropy constraint strictly satisfied Σ/² Wi, log W., log N - 1) < la)(a), and therefore Slater's conditions are satisfied.
The objective J; an affine function and therefore is convex, and the equality constraint Σ Wey = indeed affine. Finally, we will show that the constraint of the entropy inequality is convex by showing that its Hessian positive semi-definite matrix (Theorem 4.5 in (Rockafellar, 1970)). Specifically, the Hessian elements are
&
Σ
N
Wh log(Wr.) =
dWas (1 + log(Wis))
d
(79)
dW.
(80)
Wa
36

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Bigh--Dimensionl Data
2 1. d d (1+ log(Wis)
(81)
d d
N W., log(Wne)
Σ t=l
(82)
,W dWis
dW
(83)
for all j,r E (I....,N)). where j + r. As the Hessian is a diagonal matrix with positive values we can conclude that it is a positive definite matrix.
The KKT theorem states that a solution satisfying the KKT conditions-includde stationarity, primal feasibility, dual feasibility, and complementary slackness-Ba is an optimal solution to the problem, provided Slater's condition holds. To derive such solution we need to first define the Lagrangian of the minimization problem by
Ji(( (0)))L)
W is ly y
(84)
==1
N log(a) Σ
+ 6
Wr, log (Wi))
(85)
j=1
N
+
Wes
(86)
where e; and 14 IR.
solution that satisfies the stationary condition should attain for all j +
(u 1
0
(87)
dW.,
= ly
u + c (1 + log (.))) + pi
(88)
|1 y, 112 6, 14g
Wi = exp
(89)
The primal feasibility condition on the on the equality constraint induces-
W
(90)
1g:
Gi + M4
Σ
exp
(91)
J+
||
y + ci
14
exp
exp
(92)
6
6
By pushing it back into (89) get that for all j +
y W.- y, 11
exp
Wa
(93)
110 V, 13tt
Exys exp
!) 11
exp
61
(94)
Eijt exp
(-
114.- -V
37

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hiigh-Dimensiona Data
Furthermore, satisfy the primal feasibility and complementary slackness of the entropy constraint we define any e by
s.t.
Σ j
Was log Wid+ = - -log(a).
(95)
By incorporating the results from Lemma 1.1 with A, = l1 y 2 for any j E ( 1}. we get that the function E, Wes . log Wad is a non-increasing function in eç. Additionally, according the lemma, this function is bounded by log(NN 1), (d), where a; Kíj {1...... N llu, y,ll minzzi l1y, -. These boundary values correspond to the limit of the function e; oo and 0, respectively. Therefore solution e; exists only if ā; S
Therefore, based on the Marush-Kuhn-Tucee Theorem if ã; S a then an optimal assignment of ......, W is as shown in (94), with a 4 that satisfies (95). To address the optimal assignment when å; > a we use a direct approach that does not build on the KKT conditions. In this regime, any assignment of e, should satisfy the inequality entropy constraint, as the entropy function is bounded from above by log à; (Lemma I.1). Building on the suggested solution of W W.,..... W..V the assignment of e; that tends will result in the following solution
if j =
W
if and 11 - Uill = mine 11,, -vill
(96)
clsc
based on Lemma L1. This solution is valid as it satisfies the entropy constraint E, Wa, j log W., log((ā; S log(a)) it sums up to one, and W O. Now, we show that it achieves the minimal values among all solutions
W W 1
(97)
min 1y, -1ll? tfi
(98)
N Wi, Wiellys yyl1?
min W. W1,=1, -
(99)
N Wes lly, 12
min
(100)
W. Wi..0, E; Wa, lor Wis loR(o)
j=1
Hence, we can conclude the proof.
Lemma 1.2. Let M C D be smooth compact Riemannian manifold and let g -M - R2 be some smooth positive function over it. Let AM : M + IR be the Caplace-Beltrane operator over M. Then, there exists ē(M,9) .) so that for any e < E(M, 9) and & E M
1 [ exp
| (-11x
2112)
g(x))d = ( + + + AmO(v)) + +(2)
(101)
C
JaEM
2c
= g())(1+0(c))
(102)
1
(_1xx-y11) y
exp
g(xx) 2da
= cg(y) Vol)) +((3)
(103)
C JIEM
2c
= cg(v) ( V O()))
(104)
for all d E (1..... ...,,D D}. where E(x) a smooth scalar function of the curvature of M at x E M and C' = (2 (M)/2.
Proof. The proof of (101) is given in (Singer, 2006) (see Eq. 2.11). Now we begin proving (103). As x tends to y
Amg(z)( - ya)a --=y I
(105)
g(w)(<a (M) ya) (xt ua) Amg()()) ya) +2(V ya). VM(II ya)) 1--
(106)
38

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Diahhs-Dmnniin Data
((x)(ca -u)a + (ag (2 ya)
(107)
+2(xa V VMTa) + V x- 2g(=)]|V.Taal*
(108)
where we use the identity AMp- h hp + p +2(VMp, Vmhh for smooth functions p. h .M - R, as both and the restriction the manifold onto a specific dimension are smooth with respect to them manifold M. Furthermore, the fact that by combining it with the fact that the manifold is compact, we get that the Laplace- Beltramm operator and the gradients over zdd (()), g(x)) Ia are bounded.
Now, by combining it with (101) we get that for sufficiently small
/ exp
||
yl
g(x: ya)²dæ c/2(E(g) 0+ (02g()))lV O(e²)
(109)
2e
eg(y) Muall + +c2))
(110)
based on the characteristics of E.
Proposition 3.2 Let M C RR be smooth, compact, Riemannian manifold with intrinsic dimension dom(MM < D.
Suppose FI.....3 UN E M are sampled independently from smooth non- non-vanishing density f over M, and let W be defined as (1). Then, for all i E (I,....N) and sufficiently small 61.--.,6, CN E RR,, we have
W Wolly, 1
"A, G (-dim()) + O(G)) N
(6)
Proof of Proposition 3.2. For simplicity denote x - y. Let's examine the inquired term (6)
Wi, x y
(111)
exp( 1| 11,12/e;)
Σ
|| - 1,1
(112)
N1/16 CIE(I....N//6 exp( x yr 1//e)))))
exp(-1lx yl // Ø yyl2fyydd
(113)
N N-
JEM
JZEM exp( x (2)e)
where the derivation made in the last line is based on Lemma in (Hein et al., 2005). Specifically by considering A and the samples {3, bre,, where 4 = (1,.., {i}. To be explicit, in the context of the derivation, this Lemma states that: Let x M and g be continuous function on M. Then, there exists a constant C so that for any c, E (0. 1/C) such that
Σ Ejer exp(- y 1,113/)g((,) Fyemloxp(-1or 1ttp://pppl11/1///)9/////// y113/c)g(u)) 20
Pr
(114)
Σ jer exp(- 1 /2/ Ezem(exp(-11e -x|2/e))
(115)
Then, we obtain the almost-sure convergence via the Borel-Cantelli lemma as the sum below is finite for any E (0, 1), and therefore applies for 8 2 1 as well.
Ejer, exp(-lly, -,, 31113/e)9(1,)
Eye. -1t0ppppl11.11////// (00--ll///eg(00
Σ Pr 3i (1.
N
26 (116)
Ejer exp(-Ily. 12/e)
EzeM wewpleepppllll =112/e)]
N=10
Pr Ejer exp(
|| 1111//c)9(11)
Fyem/exp(-1) -yl(2/e)g(1)
>
(117)
Ejer exp(
EzeM 1|00 [c)]
N=10 1
CN2, exp(- -opp-Neemh (xp(-NeiimM)) (M) 8//()
(118)
N 10
39

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimenniooal Data
<00;
(119)
where we used Boole's inequality, and the sum's finiteness follows from its terms' exponential decay.
Next, we decompose the Euclidean distance and apply Lemma 1.2 to approximate the integral presented in (113):
I exp(-1 - IZEM exp( - 2112/s)f(2)dz
exp(-11æ:
ya ) (yy)d f(ydd
Σ
IEEM IZEM cxp(-112
212/cs)((zdd
(120)
HEM
(121)
f(z) - 0(6))
Σ
(122)
1+ O(e)
Σ
V M (1 (1+(0)() - (1+
(123)
D
6
Σ
V M
+ +0(2).
(124)
2
d=1
where we use the first-order approximation of 1/(1 = = =1=a+ 1 O(a) for sufficiently small a >> 0. Finally, by using proposition 3.1 from (Osher et al., 2017) we get
dim(M) +
(125)
and thus, the proof is complete.
Lemma L3. Let a E (1, - 1) and let {w) IR=1.C C [0, 1] a partition solution as defined in Problem 3.3. Define a set of K affinity matrices (W(l)) [0, 1|NxN by
113, y, Wile
w((k) ig
19. Ve 1 (M)
for +
(126)
ΣN
exp
else
for all ú,j = 1, 1,..., N, and K = 1,.., K where ex; atlains the minimum value that sutisfies
N
Σ
with log W( < llo(aa).
(127)
Then, a minimizer of the function G (defined in (7)) over matrices that satisfy the constraints in Problem 3.3 is
(w) arg min G((W
(k) (K)K J KK (w( JK-1 (yr . .N.)).
(128)
(W
Proof. The proof will demonstrate that the optimal solution be derived from solving NK subproblems, each corre- sponding to row of each graph solution. We will then use convexity conditions to derive the optimal solution under certain assumptions on the data. Finally, we will show that if these assumptions do not hold, the solution takes similar form, but with bandwidth parameters approaching zero.
We begin by showing that the problem can solved using NK subproblems separately. For each i E {l,..., N) and E (1....,K) K} we define a subproblem related to the row of the k-th graph matrix by
arg min
GR. (WW (h)) , (311)a1)
(129)
( 4,1
1i [(o.1)
[(0.1]
40

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Mligh-Dimensional Data
subject to the constraints W
0, Σラ= W and Σj=1 W log W S - <-oog(a), where
(8) G WW و {E
Σ lyy -y,
(130)
Based on the next derivation, we can see that the optimal solution should optimal for each of these sub-problems
min
G((W
(k)
(w) (
(131)
(
K
min
E
Σ
W iif 13y. w11
11y.
(132)
( JCONNN km s===
K
N
(k(k) 1 11
min
(133)
km
Go c(O.1]N 1=1
K
N
min
GR (K) N bj 13=1 (() (
(134)
da c(o.1j
where w! denotes the i-th row of (+),, and the domain of each minimization problem above contains the constraints shown in Problem 3.3.
that minimize the GR.; for some i E {1,..., N} and & E , K}. Specifically, we assume w:(k) 0 based on the equality to zero constraint, and omit this constraint. To find the optimal solution, we begin by building on the Karush-Kuhn Kuhh--uukeerrr (KKT) Theorem (Corollary 28.3.1 in (Rockafellar, 1970)). We note that this solution will depend on certain conditions; therefore, after this derivation, we will provide an alternative solution that attains a similar form when these conditions are not met.
Without loss of generality, we are going to find the optimal W((A) wi(k) iN
1,1
The theorem assumes that the objective and the inequality constraint is convex and that the equality constraint is an affine function. Furthermore, it assumes that there exists solution within the domain that satisfies the inequality constraint in strict manner (Slater's conditions). We begin with the latter assumption, by defining a valid solution W-(k) =1/(N- 1) for any j * and W: 0, as its rows sums up to ones. The entropy constraint is strictly satisfied Σ log [N - 1) < 4, log(a), and therefore Slater's conditions are satisfied.
i.j
W((k) log W:(k)
j=1 (,j
The objective G is an affine function and therefore is convex, and the equality constraint j= W affine. Finally, we will show that the constraint of the entropy inequality is convex by showing that its Hessian is a positive semi-definite matrix (Theorem 4.5 in (Rockafellar, 1970)). Specifically, the Hessian elements are
= is indeed
d²
w
log( (W:()) = 1tt
(1 logg (W:(
(135)
dW
dw:(1)) 6.j
(136)
((())
ij
2 1.
(137)
d
d
(h(h))
w
(k) log (A())
(1 1 +++oo (o
(138)
(k)
dw
dw
1=1
(139)
for all j,r E (1...., where j * r. As the Hessian is a diagonal matrix with positive values we can conclude that it is a positive definite matrix.
The theorem suggests that solution that satisfies the KKT conditions, including stationary, primal feasibility, dual feasibility, and complementary slackness, is an optimal solution for the problem. To satisfy its conditions we need to first define the

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dimennionn Data
Lagrangian of the minimization problem by
(
(k) N 1z=1; (*), {(r
W
(k) I1
y Vyllaa
(140)
j=1
N
log(a)) + Σ
w (K)
log log(W (W)
tek,i
2.5
==1
Σ Wr(h) -1
+Kkii
where εx, 2 0 and pogs E R.
solution that satisfies the stationary condition should attain for all j *
0 dLy,
dLW, ( 1. 13=11 (k), (1
(141)
aw(M) i.
l/., yollorrs + C21 (1 (ogg(W(()) (g)))
=
+ pkk
(142)
(()) k
1/
y, Vllla + Ck.s + pkit
=
exp
(143)
Eh,
The primal feasibility condition the the equality constraint induces-
(144)
1=1
11 U wjllarn) + ck.s + Mhki
Σ
exp
(145)
Ekit
jzi
11y:
Yy 1lasce + ck. Eh,i
exp
Pk.
Σ
exp
(146)
CK,i
j+i
By pushing it back into (143) we get that for all j *
19, 14-91 -V, 1V,lea 46.. ca,t
exp
1.
=
I1y. V. 11? Wick) tea,s ck,
(147)
Eees exp
1. -2 (1))())
exp
ck,t
(148)
I13/ - Y. 11.11 wcCk)
Edes exp
CA.5
Furthermore, satisfy the primal feasibility and complementary slackness of the entropy constraint define any cx,i by
(k)
log W((k) log(a).
(149)
By incorporating the results from Lemma L.1 with A y - 1, for any j E (I...., -1,, we get that the function Σ, w:()) log (!(k) is non-increasing function in 65,5. Additionally, according to the lemma, this function bounded by
42

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dighh-DDmensinall Data
--log(N N 1), log(() where dkg.; Ki E (1,...,,N//1} 11 yellwa mingy 1y, y Villway) These boundary values correspond to the limit of the function 6; and 6; O, respectively. Therefore solution 6; exists only if d; S
Therefore, based on the Karush-Kune Kaint-KKnn--lla Kuhn-Tucker Theorem if à S then the optimal assignment of Wa,1... W is as shown in (94), with a & that satisfies (95). To address the optimal assignment when d; > a we use a direct approach that does not build on the KKT conditions. In this regime, any assignment of e; should satisfy the inequality entropy constraint, as the entropy function is bounded from above by log å; (Lemma I.1). Building on the suggested solution of W....... W.N. the assignment of e; that tends will result in the following solution
if j=
W
if f and 11 y, wikk minez b1y, Vellwae
(150)
1
8
else
based on Lemma 1.1. This solution is valid as it satisfies the entropy constraint as Σ, W log W - log(Eu..) S
- -a),(a), it sums to one, and ([(k) = O. Now, we show that it achieves the minimal values among all solutions
N
(k) bj
13., y V
(151)
==1
min 1ff
|/y. yillare
(152)
min " E10.11E, -1 w /=1
W w
y - 1y,1um
(153)
min
W (1) WJ l1., y, Vl
(154)
W W W =0, E,
W log wi!!! -- log(a)
Hence, we can conclude the proof.
Lemma L.4. Let (1) [o, N|NN be affinity matrices under the constraints in Problem 3.3. Define a partitioning
solution (w) c 1) by
{
if k for some & E (2(d)
(155)
a
else
for d =1 1,...,, D, where (2d)) arg me... KY S(W (k) d) and S is defined in (3).
Then, a minimizer of the objective function Problem 3.3 while fixing the graph parameters satisfy its constraints
(w)
arg min G( (k) 1k=1: (0) (*))
IR=1: (V.....yy,,
(156)
Proof. The minimization problem is
D
K
N
N
arg min (k))
d
w
(k) ((xt) (Bz)a)²
(157)
d=1 k=1
As the constraints are E wa for any d = 1, D, the problem can be decomposed into / independent problems. Meaning that for any d E (1...., D......)))) D} we need to solve
(k)
N
arg min
(1) d
Σ
w
(k) ((y)a (u,)a)?
(158)
(x( 1=1
43

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dithhnioonn Data Hence, the solution this problem is
w (k)
{
i k for some & E ((d)
(159)
else
for all & E fl...., K} and d e f1,.... D), where
((d) = arg min S(W(k)) d). ke (E......)
(160)
Proposition 3.4 There exists an optimal partitioning solution {wol)) k== and corresponding affinity matrices (W(k) that solve Problem 3.3 and are of the form
k=
w(h)
exp (- 1ly,
yj
/ if i else
(9)
1.3
0
if k = le for some & E (dd)
(k)
w/
(10)
0
else
(dd = arg min
Σ (k) ke
(8) d).
(11)
for d = I,..., D and i ,,.,, N, where the bandwidth parameters {ER,i} C R4 are the minimum values that satisfy the entropy constraints in Problem 3.3, and S is the Laplacian-type score defined in (3).
Proof of Proposition 3.4. The proposition aims to characterize optimal parameters of Problem 3.3. We begin by defining two sub-problems that are related to it, each focusing on minimizing one set of parameters while keeping the other set fixed:
(W
arg min
G((W
HE
to ( (yI....,y,. NNN)
(161)
(w]t)] arg (a0))
G((W(M) I==
(6(1) J (....... yr
(162)
where the parameters limited the constraints stated in Problem 3.3.
These two sub-problems are considered in Lemmas 1.3 and 1.4. Specifically, in Lemma 1.3 the optimal graph matrices are derived in the form of
1 y 2 ",.6
(3(R)
exp
((k)
for j #
17. y, ((0)
(163)
DN exp
else
(164)
for i,j = 1..... N and le 1..... K, with Ck, that attains the minimal value that satisfies
N
w log wi(k) i < - log((a).
(165)
1=1
On the other hand, in Lemma 1.4 an optimal partitioning parameters are derived in the form of
{
1 if l 1 for some 7 2(d))
d
(b)
else
(166)
for d = 1,..., D and 1,.... K, where ((d) arg kEl......... S(W(k) (k) dd and S defined in (3).
Therefore there exists parameters of this form that minimizes Problem 3.3.
44

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimennional Data
1.2. Proofs of Section
Corollary 4.2 Let { be partitioning that satisfies the constraints in Problem 4.1. Then, graph affinity matrices that minimize (13) while fixing the partitioning parameters { (k) are
exp (- I1 1M,.-y,l (+)) (<-(1/)) 2
E exp (- <((//))E 25
1V:-U.11 if
w((
(14)
else
for i.j -,..., N and l I,.... K.
The Proof of Corollary 4.2. The proof will demonstrate that the optimal solution be derived from solving NK subproblems, each corresponding to a row of each graph solution. We will then convexity conditions to derive the optimal solution.
For simplicity we denote the following term distance term
(y yyj (1)) = 11 y/ 11ar
(167)
(1/D) EE W
(8)
This will be used throughout the proof.
We begin by showing that the problem can solved using NK subproblems separately, For each i E (l,..., N) and [I....,K} we define subproblem related to the th row of the k-th graph matrix by
arg min (W.,................ WA,, (y ........NN
(168)
W:lk) ... Wilk c(0,1)
subject to the constraints (K) 0 and Σラ= W/(k) 1. where
N (W ....... (.N) .v...... Unh) Σ r U. (k) + >>>ve
N log (
(K)
(k)
(169)
Based on the next derivation, that the optimal solution should be optimal for each of these sub sub-problems
K
min
WLN, 12 yN
W ig
log (w(h))
(170)
( (W
y Nxx
(171)
K
min
Σ
Σ
Wr 72 (V.,,, w(k)
Σ
w-(
log (w:/b)
(172)
( (W"))
Hk N
k= أ,ر=
K
N
min
Σ W/( (K) (7, 3j: (k))
Σ W log (w((1)
(173)
W.
1l0,111
K
N
min
GW. ww.. (y,.).,,,I)),
(174)
W.
E
where W (8) denotes the i-th row of (A) and the domain of each minimization problem above includes w: 0 and Ejn
for all E (l,..., K} and i (I,..., NJ.
Without loss of generality, we are going to find the optimal W((k) (x( 1,1 and & E (l...., K). Specifically, we assume W:(k) based on the equality to zero constraint, and omit this constraint. To find the optimal solution, we begin by building on the Karush- Marush-Kuhn-- Kuhn-Tucker (KKT) Theorem (Corollary 28.3.1 in
inN that minimize the Gr, for some i (1,..., N}
45

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimennional Data
(Rockafellar, 1970)). We note that this solution will depend certain conditions; therefore, after this derivation, we will provide alternative solution that attains similar form when these conditions
met.
The theorem assumes that the objective is convex and that the equality constraint is an affine function. Furthermore, it assumes that there exists solution within the domain that satisfies the inequality constraints in a strict manner (Slater's s conditions). We begin with the latter assumption, as there are no inequality constraints the Slater's conditions are satisfied.
The objective Gk.5 is a sum of a linear function and an entropy function. Based on Theorem 4.5 (Rockafellar, 1970), by showing that the Hessian of the entropy function is positive semi-definite we can deduce that is convex. Specifically, the Hessian elements
d²
N
wi(k) 1,t
log( (og(W:(k)) 1,t
(1 + log log((((()))
d2
(k)
(k)
=
dv 1.j
(175)
1=1
(176)
2 1.
(177)
d
d
Σ Wh log 1,6
log(W:(())
d
lo (o+g((((()))
(178)
dw(()) dW (k)
dw
(179)
for all j,r (1....,NN) (1/() where j * As the Hessian is diagonal matrix with positive values we can conclude that it is a positive definite matrix. Now, as the objective is the sum of two linear functions it is convex well based Theorem 5.2 in (Rockafellar, 1970) and the convexity of linear functions.
The KKT theorem states that a solution satisfying the KKT conditions-iinludiin stationarity, primal feasibility, dual feasibility, and complementary slackness is an optimal solution to the problem, provided Slater's ' condition holds. To derive such solution we need to first define the Lagrangian of the minimization problem by
N
(M) (es((W()) M
(K) (==1)
=
W
(3 y w (k))
(180)
j=1
N
(k(
(k) bg
log (w(h)
j=1
N
Σ
(1(h)
+
Pk.i
ig
-
where EARE 2 and jkk E R.
solution that satisfies the stationary condition should attain for all j + i:
0 ([.,)((W(k)) (1)()))
(181)
dW((k) (1)
(y yo: + (1 + log(w!())
+ pkk.
(182)
(- [ y w(t))) + + Mhit
((k) ijj
exp
(183)
The primal feasibility condition on the on the equality constraint induces-
Σ
W
(184)
is
j=l
46

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Diahh-DDinniinnll Data
780 My: yy: w()) + jA8.
Σ
exp
(185)
710 Myi w(k))) +e
exp
Pkii
Σ
exp
(186)
jti
By pushing it back into (183) we get that for all j # i and E (I,...,N] N)
exp
w(th) ii
=
(187)
Enst exp
:(y ;:w())))
exp
(188)
Exst exp
(->(y,
7/y, (Y Y (W()))
Therefore we can conclude the proof with the derived optimal solution form.
Lemma I.5. Let X1...., ......,,y N be random variables. Then for any >
N Pr(
N
X
S
Pr([X 2 7/N)
(189)
Proof. This lemma is not new and shown to simplify other lemmas. We begin with the upper inequality
N Pr( Σ X 27))
N
Pr
2x) Pr(3i |X 2 7/N)
Σ Pr([X, 2/N),
(190)
where the left inequality follows from the triangle inequality, the middle from set inclusion, and the right from Boole's s inequality.
Lemma 1.6. Assume the configuration described in Section 4, and let (w(k) C 1) be partitioning solution that satisfies its conditions, and E 10, Then,
K
N
11l, 12 (A)
(L/N)
log (1/(N- - 1))
Σ
exp
<(1/D) Pr Ed= w
(s,t))
(191)
8=1 1=1
j=1:jæi
(e) (1x/) 2t 1|2 + || (K+1) (K
(K+1)
N Σ
K Pk
20
(1/N)
log
(1/(N- - 1))
exp
ΣM 1=1 B.p. (b)
s=14 1=
#=1
0.8.
(192)
D.N +00
Proof. The proof will begin by first showing the uniform almost surely convergence of the terms inside the exponentials, then it will derive the above convergence. We denote the following terms that will be used throughout the proof
a((")
x
for .,... N and I...,,K
(193)
(K+1)
Buin
min .E(L....K)
8,
(194)
C max(1, 1, max || 1 2
(195)
2, Z.EEM
where M M1 x... MK+1 denotes the domain of the latent space.
47

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hlgh-Dimensione Data
We want to show the uniform almost sure convergence of the terms inside the exponentials in (191) by showing that the following quantity almost surely is bounded from above by zero.
ly. リソ 1 (K)
K
Pk
(5)
|
2 1 + ||00 [++))
23
max (. (E....,..,)
K}
(1/D)
1 Wd
(k,t)
E Sept
(K)
(196)
s=1
KKK
(6) @
10)
12
Pk 1
(0) (6) - 1/
max JJE(1...... N. k. K} J
Σ
d==1 wi
j
(197)
D)
E
D. E d=1 wd
(k)()
K (k) E
Bept
K
2d=1 Wi
(k:.0) p(() 1
(0)
(1/D,) Eden Wil
(k:38)
22
(a) 3 10
max
(198)
(.J........N AE ( K} 372
c(1/D) Dt=1 1=1 d= Wa
13 D2 (K.2)
c(1/D) Σ D3
d== Wa
D2 (k,t)
K
(1/Da) E 2d=1
(k:08 (+) T
10
Pk |جا (+) / 1011
max &E (1
K}
D. (Q/D)C/ Σ
(k.0)
é > 1 3.P1 (8)
d= W
where the first derivation introduces the problem configuration shown in (15) and the notation in (193). The second derivation uses the triangle inequality and the sub-additivity property of the maximum function. Below, we will examine these terms and then combine their results to derive the convergence.
Next, we introduce key properties of the configuration, as outlined in Section 4. In particular, the configuration governs the limiting behavior of the weighting and dimensionality parameters: (1/Da) Ed= W any s, k E [1,.... K}. Consequently, for any dg S min(3min: ve/2) there exists No. Do such that for any N 2 No. and correspondingly D 2 Do, we have
(k.,s) + (k) and Dz/D - B, for
DD/DD-BAl 5o and [(L/D,)
Σ d=1
Wd
(k,s)
[k)
S 80
(199)
Hence, we can derive the following lower bounds for all s, E (1...., .....KK K} by
Do/D 2 B. 5o 2 B. - B./2 33/2>0
(200)
D.
(1/D.)
wd
(k,s)
2 (t) do 2 Ve- Ve/2 = Ve/2>0
(201)
D. (D./D) (1/D.)
(1/D) _ w/
(kis)
Σ
w (1.)))
2 (B./2)( > 0.
(202)
d=1
We begin by analyzing the first term in (198), focusing on the individual differences that appear within the summation over 8. After examining these components, we combine the results to establish bounds on the full sum over s. The denominators in these expressions can be uniformly lower bounded using (202) by
K
D
K Σ
(1/D)
(R.0)
B.VE/4 = Ve/4>0. O.
(203)
d
1=1
1= since ΣK 8, =1
1. Hence, all of the summed elements within the first term are well-defined.
Next, we consider the numerators of the terms appearing in the summation over s, focusing on bounding the difference between the corresponding numerators. Specifically, for any e (0, 1). we bound the probability that this difference deviates from zero by
D2 3i ( E [K]:
w whath (p()) 2;11² - ||=; 221 Ed= w (kis)
Pr
Σ d=1
2 t
(204)
De
48

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Biigh-Dimensional Data
Ed=1 wa
Dr (1,e)
(VD,ple) 85))2
D2
=Pr
Ei j E [K]
- -I #,51?
2 t
(205)
Σd1 w (1,0)
Σ d== w
(2,0)
D2
SPr
3 # E &
w (v D2 (lo
(k,+))
(2: -m,))² - -1a; 11?
2 1
(206)
D,
(k.0)
1= Wd
d=1
SPr
38 ji E [N], k. E [K]:
(207)
D2
t||æc k111
W/
(k,s)
D2 1() (3: - (x;
= ||:; 15 -ē,11
(208)
Ed=l Wd
D2 (k,s)
C'
d=1
D.
PPr
3 $ j E [M] k, E [
(3, - +,y//lls - 221113 wd (v/ D3 p()) (0:
(k,e)
- 1 2 C
(209)
E d= Wd
(k,5)
d=1
(k.n) (v (VD Dyplo) (ā. - - 2,188 -1| 2 t
1
Pr
D2 (k,0) d== Wd
w
0
(210)
s,k=1
d=1
2
where [N] = (I,...,N} } and -0]=11, (l,.., K}. In the first derivation we divide by (1/D.) Ed-1 w which is within (0, 1] based on its definition in Section 4 and (203). The second and third derivations upper bound the probabilities by replacing the threshold with smaller value, following the same reasoning as before, and the definition of C in (195). Next, we invoke the independence of the samples and the assumption of a continuous sampling distribution, which implies that the probability of any two data points being identical is zero. We then apply Boole's inequality, which decomposes the events into multiple simpler events.
We can bound each of these probabilities by applying Example 2.11 from (Wainwright, 2019), which has two conditions that must hold independently for each quadruple (i, j, 8, A)) First, the entries of vD. p(+) (ā. - /////ll; - اااة should be independently and identically distributed according to (0, 1). which is attained as each entry in P is independently and identically distributed according to (0 1/D,) (see Section 4). Second, t/C should be in (0, 1), which is attained by the definition of C' in (195). Hence, the term above can be upper bounded by
2N exp
2
W ) (8009)
(k:s)
(211)
1,k=1
2N K2 exp
(212)
2N K2 exp
Dt@DeeBmiin
/00miin3//// (3202))
(213)
where we plug in (202).
By combining (203), and (213) we establish the almost sure convergence of the first term in (198) to zero via the Borel- Cantelll lemma. This is done by showing the sum below is finite for any E (0, 1), where the case for t 2 1 follows since it is bounded from above by the case f < 1.
Σ No
(N
(214)
Σ Dr (k.a) ((()) (2) (z())
(c) -
D. (k.s) (5)
((000
10)
Ed=1 We
D.
d= w
2
2t t
<(1/D) Eps dd= W (k,1)
D. D.
N
D. (kiz)
( (0) } 1)²2 D, -=
(k.
1:0e - 2 (0)13))
$ Σ
Σ
Σ
Pr
1= Wd
(215)
(1/DD Eb. Ede1 d
(k.t)
N=
N
(k.z)
p()) ( (0) / 1)2 - D,, >
(k.38) |10 (0) - 113
$ Σ
3
Σ
Pr
d d
w
(216)
cv/4
No
io
49

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Biigh-Dimensional Data
N
K
D, W
t/
Σ
Pr
(k)
(pl)) (0) - -z)-)))) 11²
(k:3)
(217)
D3 d=1
d
No
ij=lişi k=1
N
K
tc3/2
Σ
Pr
d
(k.s))
(1 (5) - -/
D
d
(k:
|| (s) - - 1|2
2
4K
(218)
N= No i.j=1:33 1:
i R,3=1
d=1
Σ
2N²K* k² exp (-f /min/ (2
(219)
No
(220)
8
Σ No
2 (P(//oo B 12 C2
(221)
<00,
(222)
where the first derivation follows from Boole's inequality. The second and third steps increase the left-hand side based on lower bounding its denominator using (203), and the definition of being strictly positive. The fourth derivation invokes Lemma I.5. Next, we apply the upper bound from (213) as 1/K,4, e < 1. The final derivation follows from the asymptotic assumption D/ (N) + oo, as stated in Section 4, which guarantees that the sum is finite.
We now turn our attention to the second term in (198), which we analyze separately from the first. We begin by examining the behavior of the numerators and denominators of the individual terms within the summation. Once these components are understood, we will combine the results to analyze the term whole. Specifically, for all k E (l....:K) K))
D2
(1/Da)
Σ
wd
(k,s)
(8) Pk
(223)
K
K (D)
K
(L/D) W
(L/D.)
Σ
Wd
(kit)
4NN
Sept
(R)
(224)
t=1
d=1
1=1
(1/D.) EB W
D.N-3cc
Pk S.pt
(225)
(L/D) EK ERs W
Dr (k.))
Σ
(3)*
where we use the algebraic limit theorem. The bottom limit follows from the two limits above it and from the strict positivity of the denominator, as established in (203).
Hence, we can establish the following limit, which bounds the asymptotic value of the second term in (198):
Edn w (k.+)) |ao("))
2 2 112
K
(2)
a
a
||2
max iJE (1........ N).KE KE jF
(1
R}
<(1 D) E Edi Wi
K
(k.))
Be0r
(k)
(226)
K
(s) 1011
(1,0)
Ed W
Pk
max
(227)
LJE N). (1 [}.....]
s=1
(1/D) ΣK 1=1
d=1
w
(k,2)
Σ
B.p.
kk)
kE(l...,K] K} E
max
C
(1/D) K
Σ
1=1
D. (k,
W
Ede d=1
Dr
w
(6.1)
Σ K
Pk
(8)
3.p
(k)
(228)
KC
1= W
(k,a)
Pk
(N)
6
max. RAKE (V
(1/D) >K
K
Ddn Dr
W
(k.4)
K
B.P.
(K)
(229)
0,
(230)
where in the first derivation we apply the triangle inequality, and in the second we invoke the definition of C as given in (195). We then use the fact that the maximum is greater than or equal to the mean. Finally, we apply (225) which establishes that for each of the ?² sequences- indexed by 8, 1,..., K converges deterministically to their limit.
50

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Dimenniooall Data
We can conclude the first part of the proof, by showing that (196) can be bounded almost surely from above by zero using (222) and (230).
1v: リソ (K) ((1/D) Ei Dd=1 wi
K
(-) Pk
3jj
D.N 0.3.
N..e K) j+1
max
(k,1)
Σ
Baps
(K)
(231)
Now, we can conclude the proof by
N
N
ly: リ 1,, (K)
log
Σ
exp
<(1/D) Ei Ede1 Wid
(k.0)
(232)
K
K
(6)
a 3. 1?
log
Σ exp
Σ
Pk
N
Σk - 3eps (8)
k=
11y,
y 12 (A)
log
Σ
exp
(233)
N
<(I/D) Σ D. >dH1 Wa
j=
1:
K
(0) | 2
log
Σ
exp
Pk
N
EE=
K
Beps (8)
Liggti
K
N
N
11 y y (K)
log
Σ
exp
c(1/D) Em Dr Dr (1.1)
(234)
k= 1=1
j=1:zzi
-d= Wa
N
K
(5) x3 - x3
Pk
-log
exp
E 1== Bip! (K)
/=1:i
s=1
| - リリ w (k)
(+) [ 5z 1|
Pk
<K-
iJE( (l........ I.... NE (1 K)
max
e(L/ Ei. Ede1
(k.()
>E 3ips (k)
K
(235)
Wd
j71
4.8 0,
(236)
D
where in the first two steps, we apply the triangle inequality together with the logarithm's 's product rule. Next, we exploit the fact that the log-sum-exp function 1-Lipschitz (see Appendix A of (El Ghaoui & Gueye, 2008)). Finally, we invoke (231) and note that K is finite.
Lemma 1.7. Assume the configuration in Section 4. Let E (0, 1), and p E (Ve, 1 -K (K - 1)Ve] and let BI, 8x E
(0, 1) that satisfy Dt Be = 1. Then, the following convergene is attained
Σ
(5)
(4)
(K+1)
(K+1)
(2)
1
log N
1
Σ
exp
x7
P6
x
-x=1 Ps
(237)
N
j iii
> Pi
K
(k)
3r
e 2 Pt
(k)
Be
K 2am1
|| | =2(0)
112p) (1)
(K+1)
2 (K+1)
2
- ps
(R)
D.N +00
0.5
Σ
EXEM
log
BZEM
exp
Pi 3e
(K)
K (k) Et
Pi
Be
(238)
Proof. For simplicity, we begin the proof by defining some terms and constants that will be used the derivations below
Σ
m=1
x
x
(+)
2
Ps
(M)
x
;
(K+1)
(K-1)
2
ΣK 1
(A)
OzJ.N.A =exp
(239)
Et=1
Pi
(k)
Br
E
Pi:
(K)
3c
51

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Bingh-Dimnnsionll Data
N
Σ
-=
k
a
(a)
x
(+)
Pa
(A)
[++1)
2. 5
(K+1)
2
Σ
x=1
ps
O
exp
(240)
N
> 1 Pi
(k)
Be
< p2. 3r
j=1j
R
|
=10)112 (K)
(K+1) 2(K+1)
2
Σ p2b1)
O₂ -EZEM
exp
E Pi Br
(k)
K <
(1)
(241)
Pt
(K++))
-2 - xK{+2) 1
Σ Ps
(K)
ΣK
||xx( - =10))12p!
Öx -ExeM
log EZEM
cxp
> Pt 3e
K (1)
6 + Pt
(1)
Be
(242)
C
max
||0 - 2112
(243)
U.E
Č exp(2CK//212)
(244)
First, We can see that E.O.J.N.A = E[O.,N,A] = Ö, where the expectations are over (z1....,,N' 2NN,/N, that are drawn independently from the same distribution. Second, we can see that Ö₁ = Pxgemoog Os,k). Finally, we can see that Ö >>> 1.
Next, we prove that the terms Oi..NNR, Oi.N.k and Öi, are bounded within [C-1,1] for each i E [I....,N] N} and A E (1....,K)) K}. A direct result of this will be that both log Öt, and Ö₁ will be bounded by [-2CK/ 0j. The terms O,,N, and Öi, are actually average or expectation operator over Ozj.N hence their bounds should be the same the latter term.
To begin with, the upper bound of Oi,,N, is 1 as the exponential argument is non-positive. As for the lower bound of N.J.NKk.
>
(A) |00 2jj
(+) (+)
1ppp (1)
2 x
(K+1) (K+1)1²
Σx
-==1 Ps
(k)
O.J.NN
exp
(245)
EK -1=1 Pe Be
E
-1=1 pi
3
|=1 Cp! (K)
CEKI (k)
exp
> Pt
(K)
Br
E Pe Be
(K)
(246)
Σx C.1
CΣK11
N exp
(247)
Ek VeBi
> Veßr
CK CK
2 exp
(248)
cve cve)
Č-1
(249)
where the first derivation uses the definition of C' in (243), and the second uses the bounds of k*)) Then, the third and fourth derivations are based on the property that Σ 3t = 1 and the definition of Ć in (244), respecitvel.
Now we are ready to use these terms to define the probability of the two terms mentioned in the statement being close by for finite N for some
K
K
Pr
log(OL.MA))
Σ
28
(250)
k=1
K
N
K
N
K
N
K
Pr
1
log(Or.NA)
1
log(O (..N.)
+
log(ō
Σ
Ö
2 8
(251)
N
N
N
k=
k=
1=1
A=
1=1
k=1
N
<
Pr
I
log(OL.NA/O..N.)
28/2
Pr
1
log (
Ok
2 2/2
(252)
N
N
A=
k=1il
where the derivations use Lemma I.5.
52

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High-Diimnnsional Data
First, we bound the second term, and then we will get to the first term. By definition, Ô = E[log(Or,k) where the expectation is with respect to æ; E M, for any i E f1....,Ny N and E KY.
K
N
K
K
N
Pr
log log(O N.....)
O 2 6/2
Pr
log log(Or.N.k) - -ōx 2 26/2K
(253)
N
k=
1=1
k=1
28 N (4K2)
S 2K exp
(254)
((oog(( 1) - -log(C-1))
(2K)(2
2K exp
(255)
1og(C-1))2
N
K exp
(256)
log(C)²
where we use Lemma 1.5 for the first derivation. In next two derivations, we use the Hoeffding's inequality along with the bound shown above that Öz,N,* E [[- 1].
Now, we bound the second term. This term is well defined as both Os,N,K and Öτ, are strictly positive as derived above.
K N
Pr
log(O log(OONN/OO.NA)) 2 8/2
(257)
k=
1=1
O,,N
Σ
Pr
log
2 6/2KK
(258)
Oz
K
N
O.NA
Oi, S exxp( (0op(-6/2x0)) Oce
Pr
2 exp(8/2K)
U
(259)
N
O
}
O - 1 exp((( 110ox((//22K011 -1}) Ouk
Pr
- 2 exp(5/2K) -1
(260)
Σ Pr
O
1 1 exp(-8/2K)
OLNN
15 -(1 exp(
exp(- (xx0)((00/221))
(261)
O
N
OLNNR
Pr
2 1 - -xp((_
(262)
Öi,
1=11=1
Oi
Pr
8
(263)
Ö
1=1
where the first derivation is based on Lemma I.5. In (261) we use the fact that exp(6)-1 = the fact that Oz,N,& can be written
>
1 exp(-6/2K) 2 0, and in (263) denote 5 = 1 ezp(- 6 8/2 Now, as an average over O...N,& and that E[...,,N. Ōz
K
N
O.,N.
Pr
2 0
(264)
K
N
N
1
Oi..N.Kk
Pr
1
2
(265)
N
Oz,
jmlozi
K N
28
< Σ
Σ
exp
(266)
1N (0/(N- - 1) - -0-1/NN11) ?
km ==1
K N
exp
(N - 11)/22)
(267)
k=1
53

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- High--Dimensionl Data
= KN exp (N2 1)/02) (
(268)
where we use the Hoeffding inequality as ON,N 10-1, 1] for all i (I....,NN N and & E {l,...,K} as noted above. Additionally, we use the bound from above to bound Oi,N, E [ ŌJ and that C 2
By combining the above results, we can conclude the almost-sure convergence in (237) via the Borel-Cantelli Lemma. applies the sum below is finite for any 0.
Pr
log(Oi,N.E) -
Σ
8k
8
(269)
N
k=1
282N
IN -) C
K Kexp
1og(Oy))
+ KN exp
(270)
NoNo
0C;
(271)
where the exponential decay ensures the finiteness of the sum.
Lemma 1.8. Let f be a non-vanishing smooth distribution over a smooth compact Riemannian manifold M and let
y M. Let .1..... 3k E (0.1) that satisfy EK Bk 1. There exists E(M. f) such that for any 22 any T 9K lVee (K 1) and any (1, (1,..., K}
| DEM
1 311390 2o
log
exp
f(x)dxx
(272)
+ -= 9:
dim(M)
K Σx
r= 9:
log
+ log (f(y)) +0(vv)
4s
and
USen exp
|
y11
ΣK go
log
f(z)dx
(273)
DEM
> 90.3e
dim(M)
K TE
1=1 903B
log
+ log (f(z)) +
Σx qs
Proof. We begin by showing (272). Based on Lemma 1.2, there exists J(M,J) S so that for any < E(M,J)
JEEM exp
x (-1o-
y/13 = f(x)dxx =
(274)
XEM
Second, if < 22 then for any E {1,...,K} K}
Ek 3
c. EK Br max dr
c.1.1
= V
(275)
qs
Ve
by using the upper bound of .1..... 9K along with their positivity and non negativity of Bi...., 3x for the first derivation, and the bounds of .I.....95 9K for the second. Therefore,
log Tre exp
(-
(-1tes 1
y 12
f(y)dd
(276)
FEM
DK grB:1
dim M3/2
log
IEe -1=1 9:3e
DK
f(x) (1 (1+0(VE))
(277)
54

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hligh-Dimensional Data
dim(M)
me 21=1 9
K
log
+ log (f(x)) + log (vo)
(278)
2
dim((M)
ITC Σ
t=1 9r
K
log
+ log (f()))++OOV)) (V
(279)
2
where we used Lemma 1.2 and (276) in the first derivation, and the identity log(1 + a) for all 2 0 in the second derivation, which follows from the identity exp(a) 2 1 +a
Now, as for (273). If < 2² then
R DE 9e
k Et
9:Br
Ve
<
(280)
E qs
min,e 9r
where the left inequality is due the nenaetiaivvty of q...... 9k. and the right uses the same derivation as in (275). Then, (273) follows using similar derivation done in (276).
Lemma 19. Let fi...., fk-1 be non-vanishing smooth distributions over smooth compact Riemannian manifolds respectively. Define to be non vanishing smooth distribution over the product manifold M
Mi X ...,, XMK+1 by fxx"))... " (l)+ II
K+1 fu(x(k)) for any (
E M.
3x E (0,1) that satisfy Σx 3x = 1. There exists f) such that for any < 2 and any q2 ......, 9K Let ,1....,BK [V,1 - (K 1)ve;
JEEn f(z)log
K II
||x((*) - 2(00
[|x(K-1) - 2(K+1)) -2(K))=(
)) f(x)dx )d= dz (281)
exp
E 9:
EK 98B
1==1
dim(Me)
log
TE
5 K 90.3
dim(MK
2 log
IEE Et K
9:31
-l())
(282)
2
ΣE 9s
where h(f) is the differential entropy of defined by h(s) --JMM lo) (ogg((2))dz
Proof. We begin by rewriting the terms inside the logarithmic term in (281) using the separability properties of M and
K
(- ||a((()
-2(0)
[I+,1++1) 2((+1))12 )) f f(x)dx
πI
log
exp
EK gr83t
(283)
BEE
K
/
||z0()) (110
= log
II
exp
fo (x)
(284)
Et 3:
[|x((K(11)
(K++) 112 DK 4s
exp
<EK 9034
Σ log ( exp
(_11z11) ||,010)
2(0)11206 9s
(285)
1== 9:.r
s=1
+ +log (Jrv-neMe exp
||x - =2(++1)122R E 9o
(x+11)
(K++1)
<E 913
Based on Lemma 1.8 there exists E(M. f) < such that for any e < 2 and qi.....44 E [ (K 1)v4 then the equation above is equal to
K
dia(Ma)
nC >K t=
g:
+ log (1.(2(01))
log
(286)
2
gs
55

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Biggh-Dimensionl Data
dim(MK+1)
log
nt
Σ
1=1
+ log (fx+)(=(kt)))+O0 + +0(V))
2
> 4s
K
(M.)
log
TC
11
K
9r.32
))
dim(Mx+1)
log
TE >E>
- 9:3r ) +og(f(z)) + O(vE).
2
9s
2
>x 4s
Now, we can push this term inside (281) and derive that it can be rewritten by
J
f(z)
Σ
K
dim(Ma)
log
wC ΣK
(288)
2
dim(MK+1)
K TE
909 1=1
log
+ log(f(z))+ + +0(v)) dz
2
> 9
K
dim(Ms)
log
TE
-1=1 90.6
+
dim( (im(MM+1))
log
TC 1=1 9:36
- -h(f)+ +Vve). (289)
2
q
2
Σx 90
k
Theorem 4.3 There exists E(M, /) S such that any e < and p E ElVE,1 (K 1)vEJ. . any partitioning solution (w) (obeying Problem 4.1's constraints) satisfies
N
log (w!!)) ))
min (Wi)e
1 eN
{w]lt)] (vit)
Σ
(1) b
K log(N -
(16)
k dim( dim(MK+1)
ΣK ps
K
dim(M.)
Ps (k)
log
+
log
(17)
N,D
2
Σ pr: Be
2
Σ Pt 3e
k,aml
K+1
dim(Ms)) log((TE) (TE)
K
ha(sa)
+0(VE)
where hfff)) = - SZEM fz(z) (og)) fo(z)dz the differential entropy of the density f. over Mg.
Proof of Theorem 4.3.
We denote the entire latent data manifold by M Mi x ... MR+1, and its distribution by ʃ defined by f(x(1) x (K+1)) = II (a())()). As can be understood, this definition complies with the data definition of Section 4.
Based on Corollary 4.2, set of affinity matrices (W(K)) K that minimize (16) is of the form:
(1)
w((k)
(290)
Σ,
for all & E (1,..., K} and i,j E (1....,
(.....N) N) and
11 -1,,-,, 12000
1 =
exp
c-(1DD) E. 201)
if
(291)
else
By plugging these affinity matrices in to (16) we get
1/ y Wikk
A (k)
(
(k)
ΣΣ
log
K
Klog(N-
-N (292)
eN
N
KK)
(1/D) 2 W
A (k)
A (k)
k=
f-==
-=1
56

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- DiahhniDnnnniin Data
K
N
K
N
N
A
(k)
A (k)
log(
A
+
log(N - 1)
+
log
(293)
N
(k)
N
ΣE=1 4,6
(k)
k=1
1,8
1=
i
1=1
1,8
(k)
log(AV 1)
(,j
log
A
(294)
A,r
==1
t=l
N
N Σ
log(N - 1) - log
(295)
N
k=
N
)
log
N Σ
A
(k)
(296)
N
1=1
Now, we can now introduce back the expressions of A for i,j 1...., N Mand I..... K and derive (17).
- lly, y, y l1am0
log
Σ
exp
(297)
N -
c. (1/D) E, wd
i=1
j=1Øjşi
(K+1) - x((+1) 12 Σx 1p! (1k)
(Jee exp
Σ
||x(()) - =2p (2)
x
0.8
log
(298)
D.N
R=1
DEM
S1== Pt Be
K (1:)
E 3
f(z)dz) Mar)da
dim(MK+1)
> Ps
K
(K)
dim( dim(MM++ log(TT))
log
K
(299)
-1= Pi
K
(K)
Be
K
dsm)
log
Pe
(k)
K
dim(Ma)
log (TT) + Kh(J) log +0(ve)
R,am1
EE
K
Pi
(K)
2
where employ Lemmas 1.6 and 1.7 to derive the asymptotic convergence in the next lines. The next derivation results from Lemma 1.9. The latter lemma indicate that there exists E(M, f) such that for any < (,M, and any (M)
ps E Ive, 1 (K 1) in which the approximation holds, where s, 1.... ....., K. Hence, we get
Lemma 1.10. Let C1, C2, C3 > 0, and 31, E (0,1) where B1 + 32 = 1. Define the function f :000.11 =0,1)² + R by
P1(1 - pp)
f(11)2)) = 1g
(300)
(p1 P282) (22 (1 31 P22
P2(1- -p2)
+C2 log
(p18) + P2)22(1 P1/11 -2-2B2)
(pI + +22)(2 -P2)
+Ca log
(p1 + P2 P1 -P232)
Let a 2 max 2. (32(1 - ( be a neighborhood constant (and therefore a 2 2). Then, for any 8 E min(3,, +e-- /a) the minimizers pi,V5 12 defined by
pi.p%
arg min
f(p P2)
(301)
(PL.22) -882
should sastisfy (pi,1)) or (p.r)) E x where I= (5, ad) and U - (1-6,, 8).
57

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hlih-Dimennionn Data
The proof will begin by determining the characteristics of function that will be used throughout the proof. Then, are going to divide the domain into different parts and prove that the value either (6, 1 6) or (1 6,,6 will attain lower value.
Proof.
We begin with going through the properties of p: [0, 1] + R defined by p(p) p(1 - p) for any E [0, 1]. The function is concave, as indicated by the negativity of its second order derivative ( see Theorem 4.5 in (Rockafellar, 1970)). It attains its maximum at p = 1/2, where its first derivative vanishes - direct application of Theorem 25.1 (Rockafellar, 1970). Moreover, p is symmetric around p 1/2. These properties are illustrated below:
df dp p(p)
d
2p -2
(302)
dp
0 = dp
p(p) = -p2
(303)
f(p)
p(1 - p) (L-p)p= f(1 (p).
(304)
For the completeness of the proof we begin by showing that 2, by showing that for any & E {1,2}
2 (32(1 -
a
(305)
2
(306)
(1/2) (12))111//)//tHHtte////
2 2-1(01+C+CC2//IC)
(307)
2,
(308)
where we use the fact that C1, C22 C3 > 0 and that is maximized at 1/2.
Now, we can begin characterizing the minimal values of f by examining its values for all (PI.P2) E [aó, 1 - a x [6, 1 - 6].
Specifically, we will show that the first two terms of f are higher than their value at (p1 P2) = (6, 1 - 5) by
Pt(1 p:)
2
8(1 8)
C log
Σ
C log
(309)
(p131 + (2 P181 - -1232)
(83) + (1 - 5))32 531 - 8)182)
1=1
[p.(1- -p.) p.)
2
(831 + (1 3) - 831 - (1 - -8)
= Σ C log
+ Σ log
(310)
8(1 5)
(pI + 32(p2 Pi )](1 P1 B2(p2 - -pi)
1=1
1=1
(a0(1 - -ad)
6((1 -5)
(53) + -11- -1-6) 10))3))(1 -831 - (1 8132) (1-5)82)
20 log
+ C2 log
+ Σ Ci
(311)
5(1 5)
8(1 8)
1/4
1=1
[a5(1 (d)) 6(1-))
(8(1 8)
[B21 (12)
201 log
+ C2 log
+ Σ C,
(312)
6(1 8)
1/4
where in the first inequality we used the concavity assumption of and that is maximized at 1/2, making p(1/2) = 1/4. In the second inequality we used the fact that + E [min( (31, 32), max(311.5 32)] as the term is a convex combination of 33 and 32. As 31 = - 32, we can see that [min(3], 82), max(31, 12)) = [min(1- - -82,, B222 max(1 - (2)] Therefore, by using the concavity assumption of p we can lower bound the numerator within the last logarithm term. Below, we continue the derivation
a(1--d))
a(1 ad)
C log
+
C log (4,8 - -B2))
(313)
2
C log (a/2)) +
Σ
Cs log (4,2(1 - B2))
(314)
2 C log (a (1/2)) + Σ
C log (B2 - B2))
(315)
i=1
58

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Hligh-Dimensiona Data
where in the first inequality we used log(1/(1 6)) log(1/1) = O, which follows from 8 min(31, B2) (tt)))+++++++++t min(31, +G+0++ 2 1 min(3), 2 1/2 from the domain of ó and that B1 + _B = 1.
/a I min(B1, B2) I 1/2. The second derivation is based on ad 2 1
As for the third terms, we will show that last term of f is higher than its value at (P1.P2) = (6. 1 6) by
(pi + (2) - P1 - P2)
(6+1- - 6 (1 -)) 6))
C33 log
C3 log
(316)
(DiBi + p2 (1 p1 1-
p2282)
(83) + (1- 81 - 831 (1 8)13))
Pr + Pp2
2 p1 P2 P2
1
=C' log
+ C3 log
-Cslog
(317)
P1 + p2B2
1 p181 P252
(63) + (1- 8)33)) (1 881 - (1 - -2)32)
Pi + P2
2 2 p1 P2
=C's log
+ C33 log
+ C's log ((03) + (1- 8) - 831 (1 - 6)32))
(318)
PI + p252
- p181 P2
Pr + PP2
2 - p1 P2
2Cs log
+ C3 log
+ Css log (32(1 - (2))
(319)
P1 + P252
- p1 P2
p1 + P222
P1 + 1 - P2
20 log
+ C3 log
+ C's log (32(1 - $2))
(320)
P111 + p252
min(p1,P2) P2)
20 log (92(1 (2))
(321)
where in the first inequality we use the same derivation made in (312), and in the second we use the fact that B1 = 1 32
(0, 1) and that P1 + S2 2 P2) which follows from it. Finally, in the last inequality, we use the fact that Pr, P2 E (0, 1).
By combining these two statements we get that f() 2 f66, 1 - 5) by
3
f(11.22) - f(0, 1 - 8) 2 1o (a/2)
+ Σ
C2 log (32(1 - (22))
(322)
i=1
(52(1 - 322) -
32) C./C.
= Ci log
a
(323)
2
(B2(1 - B2)) Eimr
:2)) C./C
2
Ci log
max (E(1,2) (B2(1 (2)) (2))
-, C./Ci
2
(324)
(B2(1 - 82)) Eim
-i C./C
2
IV IV
C log
(325)
(B22 B2)) E2 c./C
(326)
By following the same steps above and switching between Pt and P2, we can get that f attains a lower value at (p1, = (1- 5, 5) compared to it value all the points within the domain (21,P2) E [,, 1 8) x [ao, - av)).
Finally, we are left with showing that f attains a lower value at (P1. P2) (6, 8) compared any value (pI. [6, a U - ad, 1 8/2. As before, we begin by bounding the difference between the first two terms by
P:(1 p.)
8(1 8)
C
Σ C log
(327)
(p131 + (1
P1 - -2232))
(83) + (1 - 61 - 8,, - (1- - 8)182) -(1-8)82)
Pi(11 - pi)
2
(631 + (1 8))32) 831 (1-
6)182) (1-6)82)
Σ log
+
Σ
1o
(328)
8(1 - 5)
(p18) + + P131 - P232)
1=1
2
(8(1 6(1-6)
2
(63)+ (1- 83, - (1 8)332)
> Σ C log
+ Σ
Cs log
(329)
8(1 -() 5)
(pi8 + P2 p181 32)
1=1
(8(1 -01-6)
(58)+ (1 (1-8)))) 8)83) (1 - 63 - (1 - -6)82)
2 Σ
C, log
+ Σ
Ce Co
(330)
8(1-
ad(1 aτ)
1=1
i=1
59

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dimensiinnniin Data
(2 - 32) ad(1 ad)
C log
(331)
1=1
where in the first inequality we use the concavity property of p, and in the second we use its properties along with the fact that P1ś + P23 E [6, ad]² [1 - a9, 1 5/2. In the third inequality, we use the fact that 831 + (1 8),52 E (iin(31, 82), max max [81,32) as the term is a convex combination of 31 and B2. As B1 = 1 f3, we can see that
[min(3) (1i, 82), max(31, 32)] [min(1 32, B2), max(1 B2, (2)].
As for the third term, will derive their differences below.
(pi - P2) P1 P2) Cslog (p1.1 + p232)(1 P181 P222) 2C3 log((2(()) {2));
(2 (1 5))
C3 log
(332)
(631 + (1 8)83) 831 6)332)
(333)
by going through the same steps taken in (316)-(321). Now, can combine the last two results to show that over this domain f(p1.P2) P2) 2 f(,, -)
ad(1 - a6) )
B2(1 B2)
(2)
f(1. f(,, f
2
Σ
C log
+ C3 log(B2(1 32)
(334)
32(1 3,)(C(+((+(C3)
log
(335)
(ad(1 - a0))
B2(1 (2)(Ci+C2+Gaa)
2 log
(336)
Ci+02)
(01 C1tes
(B2(1 - (2))
32(1 - 3,)
= log
(337)
32(1
=
(338)
by using the concavity property of and that it maximizes at 1/2, along with the definition of 8 which Sa 32)33, CC) (Ca) < 1/2, as min(31, 32) S 1/2.
Theorem Let K = 2, and define f: (:,00) R by
dim MK(1)
Σ
K
dim(M..
psa
log
A==l
log
(18)
k=1
2
K
Pt
(k)
Be
k
Etm Pi
(K)
Be
where pi = P1 and P2 = P2 and therefore pi = 1 (1)
pi
P2
(2)
=
P2
(2)
Then, the limiting minimizer (p).p))
lime-so arg min p f(p.
either (0, 1) or (1,0).
Proof of Theorem 4.4. We begin by rewriting (18) by
f(11.P2)
(339)
2 log
dim (M.)
P
(b)
dim(Ma)
Σ
1==1 P4
(k)
log
(340)
k
>
Et=1 Pt
(k)
3R
11=1 Pe B1
(K)
dim (Ms)
Ps
(1)
ps
(2)
dim(Mss) log
2
- Pe
(1)
2
s= ps
log
+
(341)
1=1
2
1= Pi
BB
ΣL= Be
2
Σ
3g
Σ Pi
(22) 31
2
dim(Ms)
- ps
log
(342)
2
-tml Pi.
(1)
Br
Σ 1 (1 Pt )
60

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Dimhnsionnn Data
dim(Ma)
2
(1)
ps ) Σ
Ps
log
(343)
2
Ei=1
(2)
Be
Ei=1 - Pi (2)
)33, )82
2
dim M.s)
pa
1 - Ps (1)
dim(Ms)
Σ 1= Ps
(1)
2 Σ
-8= Ps
(1)
log
log
(344)
2
1=1 Pt
Be
Et=1 pi. 86
2
Σ 1== Pi Bt - Σi=1 Pi Be
(1)
(1)
dim (Ma)
Pa(1-Pa)
dim dim(Ma)
( Ps) - 1e=1Pt)
log
log
(345)
Ei= PtBi) -i= Pt.Bt)
2
( Pc.e)(1 Ei=1 Pc.t)
where in the second derivation we use p.²) = (1) for 1, 2, as defined in the theorem's 's statement. Then, we use
Σ Br 1 defined in Section 4, and substitue p.d ps defined in the theorem's is statment.
We observe that the function f(p1, P2) matches the form analyzed in Lemma I.10. Therefore, there exists constant > 2, dependent on $1, M1, MM, such that for any sufficiently small 8 > 0, the minimizers of f over the domain
[6, 1 -j8 lie within either L x U or U L, where L = [6, aσ) and = [1 aτ, 1 - 6]. This implies that, for any sequence of minimization problems with os that tends to 0, the corresponding minimizers converge to either (0, 1) or (1,0). By setting 5 ve and similarly considering a sequence of problems with es that tends yields the desired result stated in the theorem.
61

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Highh-Dimensiona Data
1.3. Proofs of Appendix C
Lemma 1.11. Let (W c [0, 1o.1 be affinity matrices under the constraints in Problem C.I. Define a partitioning solution (w) C [0, 1 by
exp (-E W(k) (o))a-(Uj)aa)
w
k: K.
(346)
EEy= W() ((Vi)a - (om)))-(,))a))))) 18)
exp
Then, minimizer of the optimization problem suggested in Problem C.I among partitioning solutions that satisfy its constraints is
(0))) w()) = arg min Greg (6. (W0) 1k=1 1m (y.) (1)(1))
(347)
Proof. The proof will demonstrate that the optimal solution can be derived from solving D subproblems, each corresponding to coordinate of partitioning solution. We will then use convexity conditions to derive the optimal solution under certain assumptions on the data. Finally, we will show that if these assumptions do not hold, the solution takes a similar form, but with bandwidth parameters approaching zero.
We begin by showing that the problem can be solved using D subproblems separately. For each d [I,..., D) we define a subproblem related the d - th coordinate by
arg min Ca((W(()) 1K=1, (2 1k=1: (u,1)=1) (...(())
(348)
(K)
subject the constraints
Ed= a 1, where
K
(a((W(())) 1m K
(K 1k 15
Σ
Wd
(k)
ΣΣ
w ((y)))-(1))))))) -(9))a)2
(349)
R=
log (ma
5
W
(350)
Based on the next derivation, we can see that the optimal solution should be optimal for each of these sub- babb-pooblmms
Greg(d, (k) ) I 1
min
(351)
(
D
K
min ( JK
G((W(()) ), (, (u.) +6
()
w d
log(E(())
(352)
d=1 1=1==
K
min J (
Σ
w/(h) b.j
13 3 1112000 8
Dlog(K)
(h) (a)))
(353)
11j=1
d=1
D K
N N
D
K
min k E= d=1 k=1
ΣΣ
(k)
ΣΣ
iif ((y))a ( - (y1,)a)²
log
(k)
(354)
d
a
d=1 k=1
K
N
D
K
min
wh (k) bi
((y))a - (z)))a}
log
(355)
(1)
K
k=1
D
K Σ
Σ
(allW (
(2) 1
J 1
(356)
1=1
where the domain of each minimization problem above contains the constraints shown in Problem C.I.
62

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of Highh-iimnnsiona Data
Without loss of generality, we are going to find the optimal wa .....w. (K) that minimize the G. for some d E {l...., ......,D, D}. To find the optimal solution, we begin by building on the Karush-Kuhn KuunTu (KKT) Theorem (Corollary 28.3.1 in (Rockafellar, 1970)). We note that this solution will depend on certain conditions; therefore, after this derivation, we will provide an alternative solution that attains a similar form when these conditions are met.
The theorem assumes that the objective is convex and that the equality constraint is affine function. Furthermore, it assumes that there exists solution within the domain that satisfies the inequality constraints in a strict manner (Slater's s conditions). We begin with the latter assumption, as there are no inequality constraints the Slater's conditions are satisfied.
The objective Go is a sum linear function and an entropy function. Based on Theorem 4.5 in (Rockafellar, 1970), by showing that the Hessian of the entropy function is positive semi-definite we can deduce that is convex. Specifically, the Hessian elements are
dc
K > k=1
log (a))1)
=
6(1 + log((>()))
(357)
d
did
(358)
2 0.
(359)
K log
dāole
dās
Σ wd
(k)
=
dā
5(1 + log(() (k)
(360)
k=1
0
(361)
for s, k [I,...,K] K where + k. As the Hessian is diagonal matrix with positive values we can conclude that is positive definite matrix.
Now, as the objective is the sum of two convex functions it is convex as well based on Theorem 5.2 in (Rockafellar, 1970)
and the convexity of linear functions.
The KKT theorem states that a solution satisfying the KKT conditions- conditions-includingg stationarity, primal feasibility, dual feasibility, and complementary slackness-is an optimal solution to the problem, provided Slater's condition holds. To derive such solution we need to first define the Lagrangian of the minimization problem by
(a(W((), (a(W
(R)
(k) ((v,)a (v,))a
(362)
d
k=
(k)
log (w)
+
W
k=1
K
(k)
+ H4
1)
k=1
where pa E R.
A solution that satisfies the stationary condition should attain
0 dLa
(363)
dus
(K)
N
Σ M
(():) (1,))))² 5(1 log(w (1)))) pd
(364)
Σxj=1 w((h) ((zr)) (z))))2 +8 Hd
(k)
w/
exp
(365)
8
63

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Diahh-Diinniinnll Data
The primal feasibility condition the the equality constraint induces-
(k)
(366)
N N
Σラ
((y:) - (U))d)² + pd
exp
(367)
6
R=1
E Σز ا
(K) (Wy: (2) +
exp
Ad
Σ exp
(368)
K
Σn شروز N.
( ((yn)a (U,)a)2 5
Pd
=
8 log
exp
(369)
k=1
By pushing it back into (365) we get that for any & E []....,,
ΣN ΣN (1y (y
exp
(k)
w
(370)
Σ exp
Eis Ei W (1) )a U D213
exp
(371)
K Ek=1 exp
Ei Σ ( )a 19 10)2
Therefore we can conclude the proof with the derived optimal solution form.
Ja=1 C [o, 1]. be partitioning weights and { k=1. C [0, 10,1] be affinity matrices that satisfy the constraints of Problem C.I.
Proposition C.2 Let 5 2 0, (w {
Define (k) c [0, 1j as in (9) based on (A) ]== and (k)) 1K
Tk=l by
(K)) exp En, Wib ((y))a - (w,)4) ( w
K
Ees
((ya)a (3)))d) W(() bi
Σ 8=1
exp
(21)
Then, we have that
(W())))) arg min Greg (6, ( (k) 1k=1 ( (..)
(22)
(
(W) arg min Greg (6, (W IK=I (~()) (1))
(23)
(1)
Proof of Proposition C.2. The proposition aims characterize optimal parameters of Problem C.I. We begin by defining two sub-problems that related to it, each focusing minimizing set of parameters while keeping the other set fixed:
(W(())))
arg min Greg (5, ( K (K), (v.)
(372)
(W"))
(b))) = arg min Greg (5, (W()) j ( (.. (1)t))
(373)
where the parameters are limited to the constraints stated in Problem C.I. Interestingly, the suggested optimization problem in (373) can be rewritten by
(w()) = arg min Greg ( (W(() (K),K
J (k)
Sk=1 (
(374)
(W
64

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High Dimhnnionn Data
P
K
arg min G([ (1)) (6 (. + (log(()) + (W")
Σ d=
(R) d
log(E/ (10)
(375)
k=1
arg min G( G( (1) (W
(.
(376)
These two sub- problemo considered in Lemmas 1.3 and 1.11. Specifically, in Lemma 1.3 the optimal graph matrices derived in the form of
1y. 1
exp
(k) tg
for j +
13. V. ()))) s,,1
(377)
EN
1i-1
else
(378)
i.r = =,,,,..... I,..., N and k = I,... K, where εxii attains the minimum value that satisfies
N log w!bh I -log(a).
(k)
(379)
the other hand, Lemma 1.11 an optimal partitioning parameters are derived the form of
(- (-EN W(N) ((ya)a - (w)))) 18) Σ
exp
(380)
K Ek=1 exp
Em W( ((y,)a (2,)a) /6)
for d = 1,..., D and & = 1,.... K.
Therefore there exists parameters of this form that minimizes Problem C.I.
Proposition C.3 Let ( JK c [o, lI be a soft uniform partitioning, i.c. wh)) = 1/K, and let (w())
/==1 be the jk=1 be the optimal partitioning
corresponding affinity matrices from Proposition C.2. Let (w) k {0, 1 and (w()) ( solution as discussed in Proposition 3.4.
Define
G((W
IK= (K) Ik=1 (w.)
(24)
D 1.-log (K)
Then, for any hard partitioning solution (x(K) jkmi C {0, 1 and any corresponding affinity matrices { { ( have:
(k) 1K
Jkmi we
Greg(Smntt (Smit:
K 1=
( 1m (v.) S GreglEmnit { (k) K
1m=1 (k) 1s (v.1
(25)
Proof of Proposition C.3. We can see that the inequality stands based on the following derivation-
Greg (inits
(k)
) K (D
(381)
D K >>
GK(
K= 1u Senis
Dlog(K)+
a log(
(382)
1k=1
(k( Jk=1
(K) K
(1) 1 (
(383)
dinie(D (D. log(K))
(384)
65

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Diahh-Dimnniinnl Data
G([ K IREI (o (K)
1= (u)) + denia (D Mog(K))
(385)
D
K
G((W
J JR ) (u:) + dinit
Dlog(K)
+
(R) d log(E/
(386)
d=1k=1
Greg(Oinit) (W M== (60
Ik=1 (Br
(387)
where in the second derivation we introduce the identity Ek= Wa log - log(K) K) for all d E {I...., D)....,), which holds by definition of the uniform partitioning. In the third derivation, we introduce the definition of ōma.. Then, in the fourth derivation the non-negativity of G, along with the identity Σx= wd log Tog 0 for all E (1...., D), which follows directly from the definition of hard partition.
(k)
(k)
Proposition C.4 Let the data consist of N data points in RDD Then, the computational complexity of obtaining the partitioning weights {w)
1== and the affinity matrices { (W(())) I== as defined in Proposition C.2, is O(K
Proof of Proposition C.4. The feature partitioning weights, (w)())), described in (21), are constructed based on:
N
Σ
w (K) is ((vi)a (21))a)²
(388)
for every d E (1......0. D} and k (1,..... ........... KJ. The computational complexity of evaluating this quantity is O(N2) for a specific d E (1,...., and (1..... K). and overall O(N2 for all. The remaining operations used to define the feature partitions taking the exponential of this value and normalizing across partitions result in a computational complexity of O(DK). Therefore, the overall computational complexity of this step is OK)
We now derive the computational complexity associated with computing the affinity matrices. These matrices are constructed based on the following weighted squared distances:
ly ne,-yyllee Mylla
= Σ
((ye)a (y;)))))) wa d=1
(R)*
(389)
for all i,j E {I...., ] and E {l,.... KJ. The computational complexity of evaluating its value is O(D) for a specific j E (1.....N) and k E [1....,'] K}. and overall O DK) for all. The remaining operations used to construct the affinity matrices involve taking the exponential value of each distance and normalizing across j E {1,..., J.....,J, N). for every E NN and {I....,k] K]. These operations attain computational complexity of ON Therefore, the computational complexity of this step is O(N² (K).
Now, by combining the computational complexities for both parameter updates results in O(KN2D).
Proposition C.5 Let the data consist of N data points in R.P. Suppose the data is given in the form of singular value decomposition (SVD) approximation of rank S < N, D. Then, the computational complexity of obtaining the partitioning weights (A)) 1K =k=1 and the affinity matrices { [ (k) K Ik=1, as defined in Proposition C.2, is (SK N² S²
Proof of Proposition C.5. Let Y E NDD represent the data matrix, with the points embedded as rows. The SVD approximation is given by Y UEVT, where U E N and V E DxS are the left and right singular vector matrices, respectively, and E SxS is the diagonal matrix of the leading singular values.
The feature partitioning weights, (w)l))), described in (21), are constructed based on:
N
Σ
w (h) ((t:)a (21)))²
(390)
for every E (1..... D) and l: E (1,..., ......,,K ,K). The remaining operations used to define the feature partitions taking the exponential of this value and normalizing across partitions - result a computational complexity of O(DK). In the next lines we will rewrite the equation above and compute the computational complexity associated with it.
66

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- High--iimeniioal Data
We begin with rewriting the (390) by
W (R)+ ((yi)a (3)))))
(391)
w (1,))
(k)
(v,)) -2 Σ
w(k (2,)a(y,)a
(392)
1=1
1,j=1
N
N
(k)) ij
+ ( ) Σ (Wr()) + W (y))
(1)
(393)
:-=1
= (Y (diag( W (8) 1 (w (K)) 1)) (all) )ddd - (Y' (W + (W) a
(394)
( )ad
(395)
where (4) E NNNN is defined by (*) = diag( (W())+ + (W(()))7) - (( - (w(*))) for any l E (I...., K). the vector E R.N is an all ones vector, and diog: T + RNN generates a diagonal matrix from a given vector. The construction of L (k) using (k) is O(N)).
We now incorporate the singular value decomposition (SVD) of Y into this expression and derive its computation complexity by analyzing the matrix multiplications involved:
(VEUT L ( ( )a.a.
(396)
Define (k) = ( E RRS The computational complexity of computing it is O(SN2 + N2 as U E RNN and (M) E RNN, Next, define ( = EA (k) E E RSx5, Since E is a diagonal matrix, the computational complexsity of this multiplication is O(5²). Therefore we are left with computing:
(V (k) V )ddd
(397)
The computational complexity of evaluating each such element is O(5²) for each d E (1....,D) D), and overall O(5
Therefore, the computational complexity of evaluating (390) for given & E (1...., K} is OSSN2 + D). Thus, we can conclude that the total cost deriving the feature partitioning weights is ((K(SN2 + +DD + DK) = O(K(S22 + D))
We now turn to deriving the computational complexity of the affinity matrices. As described in (14), these matrices are constructed based on:
ly, yy W())
(398)
for all i,j {L,..., N} and k E {I,...,K} K}. The remaining operations used construct the affinity matrices involve taking the exponential value of each distance and normalizing across j E [1,...,.V] NY, for every i E {l,..., .N and k E (1...., K). These operations attain computational complexity of O(N2K). In the next lines we will rewrite (398) and derive its computational complexity.
We now incorporate the singular value decomposition (SVD) of Y into this expression and derive its computation complexity by analyzing the matrix multiplications involved:
l1. -y,llaca -(Y (w) )x, + -UUEV" diag (K)) (1)) SAS''VEEE'' EU"),, )₂, + (UEV* diag(w VEU" )53 2UEV diag(w (8) (8-)) VVE )ay
(399)
(²)) 2(Y (w) )a
(400)
(401)
for all i,j E N} and k E (l,..., K}. where diag: RD + DXD generates a diagonal matrix from given vector. (k) V (k)) RSx8 Its computational complexity is D) V R Dx8, Next, define F(()_ (k)() E E RxS Since E is a diagonal matrix, the computational complexity of this multiplication is O(52).
Finally, the computational complexity of (V'FFU V)a, is O(5?). and the computational complexity of deriving it for all entrees OS5
67

---

Partition First, Embed Later: Feature Partitioning for Refined Embedding and Visualization of High- Tligh-Dimensional Data
Therefore, the total computational complexity for evaluating (398) for all i, fI,...,,N N] for a given k {I,..., K} O252 + D). Thus, K² = ((K(5 + D)). Now, by combining the computational complexities for both sets of parameters we get: + K( + D)) = O D).
conclude that the total cost deriving the affinity matrices is OKK +
68


Reviews:
[{"review_id": "6AFQIXDc4T", "reviewer": "Reviewer_zz3i", "summary": "The manuscript proposes a new dimensionality reduction method, targeting the case where data feature originates from K sets, which are either independent or low-dependent. The method is composed of two steps. In the first, a decomposition of the data features into K disjoint sets is identified; in the second, a classic dimensionality reduction method is applied to each of the K subsets. The decomposition generalises upon a common first step in existing methods, which uncover a graph structure (\"Laplacian\") from the data disimilarity matrix. Here, both the decomposition into K sets and the smoothness objectives are co-optimised, achieving better smoothness than the original frameworks. The method is demonstrated to be brilliant on synthetic data, which was created by the assumed generative model, and superior to previous approaches on certain real-world problems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their time and thoughtful feedback. We appreciate that the reviewer found our claims to be \"supported by clear and convincing evidence\" and that our \"theoretical claims are beautifully supported with clear explanations and detailed proofs.\" \n\nQ1. Does your method help mitigate the criticism of \"The specious art of single-cell genomics\" (which you nicely cite as motivation for your method)? Or does the criticism equally apply to your method as well?\n\nR1. Our approach addresses some of the criticisms outlined in \"The specious art of single-cell genomics\" but not all of them. Specifically, substructures in the data that have low intrinsic dimensions could be embedded more accurately after our proposed partitioning. This advantage is demonstrated in our simulations and experiments. However, even if our approach successfully partitions the features into groups representing distinct substructures, there is no guarantee that these substructures can be accurately visualized in 2 or 3 dimensions. Nonetheless, even if the visualization fails, the partitioning obtained by our approach can be used for many other analytical tasks beyond visualization. Hence, the core of our approach, which partitions the data into simpler structures (regardless of visualization), is less susceptible to the criticism of \"The specious art of single-cell genomics\". To clarify this issue in the text, we plan to add this explanation to the discussion section.\n\nQ2. Can you offer an objective criteria (a test) for when your method is expected to perform better than previous ones? Obviously, for the correct data generative model, this is the case, but can you offer some guidance for someone running the method on real-world data?\n\nResponse. We refer the reviewer to the second paragraph of page 20 in appendix G.\n\nQ3. What are the limitations of the proposed algorithm on data which does not satisfy the assumptions (e.g. K=1)? In what sense would your approximation degrade the results of classic dimensionality reduction methods?\n\nResponse. In cases where the data consists of a single smooth structure and is partitioned into K>1 feature groups, we expect that the partitions will each capture a structure similar to the original data, at least in the model we analyzed in Section 4. This will result in redundant embeddings that are similar to an embedding using all features. In Section G of the appendix, we explain it in more detail, along with other related scenarios of over-selecting or under-selecting K.\n\n*Response to other comments and concerns:*\n\n(Experimental Design). The methods' demonstration in terms of visualization is straightforward, while other evaluations of the experimental results are barely done (beyond what is shown in Table 2).\n\nResponse: We refer the reviewer to our response to Question 1 from reviewer 92va.\n\n(Other Streng. And Weak.). Only a single real-world example is presented in the main test and another in the appendices.\n\nResponse. Based on the reviewer comment, we conducted a new experiment using a liver scRNA-seq dataset [A] that contains two biological organizing factors: the circadian cycle process and cellular zonation (spatial organization of cells in liver layers). The data consists of 6,889 cells, where each cell is annotated by the circadian time at which it was captured (ZT00, ZT06, ZT12, ZT18), which follows a cyclic pattern, and its location within the liver (Layer 1-8), where cells from adjacent layers share biological relationships. We apply standard preprocessing on the data before applying our partitioning approach. A comparison of the traditional tSNE embedding with tSNE embeddings based on the extracted partitions is provided in https://anonymous.4open.science/r/FP-70F4/\n\nThe comparison includes:\n* liver_circaidan_PCA10 - This figure demonstrates how the circadian process is reflected across different embeddings. \n* liver_layer_PCA10- This figure illustrates how the zonation is captured in the embeddings, by overlaying each layer subpopulation separately on top of the entire embedding.\n* Note: The \"PCA10\" indicates that we used PCA with ten dimensions within the preprocessing. Additional files ending with ``PCA20’’ are included as well, and in these we used PCA with twenty dimensions.\n\nTo conclude, the traditional tSNE embedding provides a single visualization where both processes are shown together. While the embedding contains four clusters, the cyclic structure defining the circadian cycle is less evident. However, the embedding based on Partition 2 does reveal both clusters and the cyclic structure. Additionally, while zonation is visible in the traditional t-SNE, it appears less distinct compared to the clearer and more progressive representation of zonation in the embedding based on Partition 1, which aligns better with the zonation layers.\n\n[A] Droin, C. et al. Space-time logic of liver gene expression at sub-lobular scale. Nature metabolism 3, 43-58 (2021).", "claims_and_evidence": "As far as I could see, all claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Evaluation criteria are hard for dimensionality reduction methods, and the proposed method might be superior in certain cases and inferior in others. The manuscript does not compare the new method with previous ones using the subfield common (albeit not well justified).", "theoretical_claims": "The theoretical claims are beautifully supported with clear explanations and detailed proofs.", "experimental_designs_or_analyses": "The methods' demonstration in terms of visualisation is straightforward, while other evaluations of the experimental results are barely done (beyond what is shown in Table 2).", "relation_to_broader_scientific_literature": "The manuscript provides a great literature review of both dimenionality reduction methods and graph decomposition methods.", "essential_references_not_discussed": "None that I could see.", "other_strengths_and_weaknesses": "Strengths \n * Clear motivation and superb depication of the inner working of existing methods. \n * Very nice proposal of the objective function we wish we could solve and several relaxations toward an objective we can solve.\n * Proofs for the convergence of the algorithm to the correct solution in certain cases.\n\nWeaknesses\n * The results are mostly aesthetic and subjective rather than through improvement of a previously-proposed benchmark (beyond the results in Table 2 which are quite minimal).\n * Only a single real-world example is presented in the main test and another in the appendices.", "other_comments_or_suggestions": "My score is only \"weak accept\" rather than \"accept\" due to the limited evaluation of the method.", "questions_for_authors": "* Does your method help mitigate the criticism of \"The specious art of single-cell genomics\" (which you nicely cite as motivation for your method)? Or does the criticism equally apply to your method as well?\n * Can you offer an objective criteria (a test) for when your method is expected to perform better than previous ones? Obviously, for the correct data generative model, this is the case, but can you offer some guidance for someone running the method on real-world data? \n * What are the limitations of the proposed algorithm on data which does not satisfy the assumptions (e.g. K=1)? In what sense would your approximation degrade the results of classic dimensionality reduction methods?", "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": "jzXAy15eGa", "reviewer": "Reviewer_2zX4", "summary": "The authors propose an approach for embedding high dimensional data via partitioning features using a Laplacian smoothness optimization. This improves over classical techniques for embedding where extreme dimension reduction can distort results. They provide theoretical results characterizing the solution of their stated optimization problem as well as related asymptotic analysis. They provided experiments that examine the efficacy of their approach in real data.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your thoughtful and positive review of our paper. We are pleased that the reviewer found our approach ‘original’ and that they considered the paper’s contribution to be “sufficiently impactful and significant”. Additionally, we appreciate the reviewer's recognition of the “clarity” with which the paper is written, as well as their acknowledgment that we did a “good job”  with the simulations in Table 1 to compare our results with other algorithms.", "claims_and_evidence": "Yes. Theory is sound to the best of my knowledge, and experiments are rather comprehensive.", "methods_and_evaluation_criteria": "The comparisons provided in table 1 and in appendix section G are sensible.", "theoretical_claims": "I did not check the proofs of the theorem that are in the appendix/supplement. However, to the best of my knowledge, the theorems appear sound and I did not find any mistakes in the theorems in the main text.", "experimental_designs_or_analyses": "Given that the approach proposed is unsupervised in nature, it is indeed challenging to validate. The authors did a good job with the simulations in Table 1 where they compared their algorithm with others under a simulated setting where partitioning error can be measured.", "relation_to_broader_scientific_literature": "In terms of broader science, there is a large literature in machine learning on manifold learning and dimension reduction. In biology, such methods are often used to analyze sequencing data to uncover new cell types etc.", "essential_references_not_discussed": "To the best of my knowledge, the literature and prior work that are essential have been cited in this paper.", "other_strengths_and_weaknesses": "originality: The approach of partitioning features is original, to the best of my knowledge, regarding dimensionality reduction.  \n\nclarity: The paper is written clearly. The material is naturally challenging, but the authors did a good job of exposition. \n\nsignificance: given the broad applications of dimensionality reduction, I find the paper's contribution sufficiently impactful and significant.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "VPyngGPZ5W", "reviewer": "Reviewer_E6QD", "summary": "High-dimensional data can sometimes be composed of multiple sets of features, each following a distinct substructure. Traditional visualization methods such as t-SNE, when applied to the full feature set, struggle to capture these substructures. The authors propose a method that enables feature space separation for improved visualization of individual feature sets. Both qualitative and quantitative results suggest that the proposed method outperforms existing baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thoughtful and detailed assessment of our work. We are pleased that the reviewer found our \"proposed method and evaluation criteria well aligned with the problem at hand\". We also appreciate the acknowledgement that \"most claims in the submission are clear and supported by evidence\".\n\nQ1(Q. for authors). Appendix G describes the procedure for determining the number of partitions in a dataset. However, the proposed elbow method may fail when the optimal K is 1, potentially leading to spurious partitions. How do the authors mitigate this issue?\n\nResponse . We propose a suitable test to address this challenge in the second paragraph of page 20, Section G in the appendix. This test is designed to assess whether the data should be partitioned into two subsets (K=2). It compares the smoothness score (Eq 8) obtained from partitioning the data with an analogous score obtained from a randomly transformed version of the data, which mixes the features. This transformation simulates a scenario where no partition is possible. A significant difference between the two scores suggests that the data can be meaningfully partitioned.\n\nResponse to other comments and concerns:\n1.(Other Comments) Algorithm 1, which is central to the proposed method, is only provided in the supplementary material. While this is likely due to space constraints, summarizing the approach in the main text would improve readability for the audience.\n\nResponse. We agree with the reviewer, it was indeed excluded due to space constraints in the initial submission. We will add such a summary at the end of Section 3.2. We refer the reviewer to our response to Q2 of reviewer 92va.\n\n2.(Other Comments) “The authors should further emphasize the importance of the problem to strengthen the motivation for the method”.\n\nResponse. We thank the reviewer for this comment. To strengthen the motivation for our method, we will add the following discussion to the introduction section (specifically in page 2, between the first and second paragraphs in the left column):\n“The setting where distinct feature subsets of the data may contain unique geometric structures is widespread in applications. For example, in hyperspectral imaging, different feature groups correspond to different wavelengths, which capture distinct chemical or physical phenomena of the observed materials or environment [A, B]. Similarly, in astrophysics, different spectral bands of electromagnetic radiation serve as feature groups in the data, capturing distinct astrophysical phenomena such as interstellar extinction, fast radio bursts, and gravitational waves [C,D]. In cellular biology and genomics, different groups of genes may be associated with distinct cellular processes [E,F], as we exemplify in Section 5.2.”\\\n[A] Khan, M., et al. \"Modern trends in hyperspectral image analysis: A review,\" in Ieee Access, vol. 6, pp. 14118–14129, 2018.\\\n[B] Lu, B., et al. \"Recent advances of hyperspectral imaging technology and applications in agriculture,\" in Remote Sensing, vol. 12, no. 16, pp. 2659, 2020.\\\n[C] Indebetouw, R., et al. \"The wavelength dependence of interstellar extinction from 1.25 to 8.0 $μ$m using GLIMPSE data,\" in The Astrophysical Journal, vol. 619, no. 2, pp. 931, 2005.\\\n[D] Burke-Spolaor, S., et al. \"The astrophysics of nanohertz gravitational waves,\" in The Astronomy and astrophysics review, vol. 27, pp. 1–78, 2019.\\\n[E] Sastry, A., et al. \"The Escherichia coli transcriptome mostly consists of independently regulated modules,\" in Nature communications, vol. 10, no. 1, pp. 5536, 2019.\\\n[F] Kotliar, D., et al. \"Identifying gene expression programs of cell-type identity and cellular activity with single-cell RNA-Seq,\" in Elife, vol. 8, pp. e43803, 2019.\n\n3.(Experimental Design)  The experimental design seems legit, but the number of datasets examined is relatively limited. The main text evaluates only three datasets, two of which are simulated. The supplementary materials primarily contain additional simulated datasets based on object rotations. Expanding the evaluation to different modalities or another scRNA-seq dataset would help validate the broader applicability of the method.\n\nResponse.  We refer the reviewer for the Response for (Other Streng. And Weak) to reviewer zz3ii. Additionally, during the revision period, we commit to enhancing our manuscript by incorporating analyses using datasets from the paper\n\nQu, R., et al. \"Gene trajectory inference for single-cell data by optimal transport metrics,\" in Nature Biotechnology, pp. 1–11, 2024.\n\n4.(Experimental Design) Visualizing the separated datasets using methods beyond tSNE could provide further insights into the effectiveness of the proposed approach.\n\nResponse. To address the reviewer’s concern, we will include UMAP and Diffusion Maps embeddings in the Appendix for additional visualization and analysis of the separated datasets. The images can be found in https://anonymous.4open.science/r/FP-70F4.", "claims_and_evidence": "Most claims in the submission are clear and supported by evidence. However, the prevalence of substructure concatenation in real-world datasets beyond the simulated examples (rotated figurines/COIL-20) and single-cell transcriptomics is not thoroughly discussed. Additional insights into its occurrence across diverse applications would strengthen the motivation for the proposed method.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria are well-aligned with the problem at hand.", "theoretical_claims": "The proof in Appendix I appears sound, with no major issues identified.", "experimental_designs_or_analyses": "The experimental design seems legit, but the number of datasets examined is relatively limited. The main text evaluates only three datasets, two of which are simulated. The supplementary materials primarily contain additional simulated datasets based on object rotations. Expanding the evaluation to different modalities or another scRNA-seq dataset would help validate the broader applicability of the method.\n\nAdditionally, visualizing the separated datasets using methods beyond t-SNE could provide further insights into the effectiveness of the proposed approach.", "relation_to_broader_scientific_literature": "The proposed method addresses high-dimensional data visualization in cases where the dataset can be decomposed into multiple substructures. While this approach is likely valuable for computational biologists, its broader applicability to other fields may be limited (see my comments in Experimental Design and Analysis section).", "essential_references_not_discussed": "I'm not aware of any essential references that were not discussed.", "other_strengths_and_weaknesses": "The paper is well-written, and the figures are clear and visually appealing.", "other_comments_or_suggestions": "Algorithm 1, which is central to the proposed method, is only provided in the supplementary material. While this is likely due to space constraints, summarizing the approach in the main text would improve readability for the audience.\n\nThe authors should further emphasize the importance of the problem to strengthen the motivation for the method.", "questions_for_authors": "Appendix G describes the procedure for determining the number of partitions in a dataset. However, the proposed elbow method may fail when the optimal $K$ is 1, potentially leading to spurious partitions. How do the authors mitigate this issue?", "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": "vWib7Vdj9k", "reviewer": "Reviewer_92va", "summary": "This paper claims when the data is complex and governed by multiple latent variables (which is almost always the case), the visualization methods that aim to capture all features in single lower dimensional space often: fail in disentangle the latent variables, or requires larger dimensionality to capture the full structure in the high dimensional data. To address this issue, this paper assumes the dataset is generated by mutually exclusive  manifolds each corresponds to a subset of features, and proposes to first partition the feature space into sub spaces, by minimizing Laplacian score of the partition and then perform DR w.r.t each subset of the features. The paper provided an extensive theoretical analysis of the partition problem and provided an alternating optimization algorithm that obtains soft assignment score which approximates the hard assignment solution. In the experiment section, the proposes approach is compared against multiple clustering methods (over features) on a synthetic dataset. Also, the approach is compared against tSNE on identifying biological processes in RNA sequencing data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1. “Could you compare the proposed approach with stronger baseline mentioned above?”\n\nR1.To address the reviewer’s concerns, we conducted a comprehensive comparison of our approach with the methods [A], [B], and [C] using the biological dataset from Section 5.2 and the rotating figurines dataset in Appendix D. It will be incorporated into the text.\n\nWe now explain our quantitative error measure for the biological dataset. To compute an error measure for a given embedding of the dataset, we do the following. For each point (cell) i and each of the two types of labels (cell phase and type), we find the k nearest neighbors of point i and compute the proportion of nearest neighbors whose label differs from the label of point i. This provides two scores (of label inconsistencies) for each point, corresponding to the two processes. We then average these scores across all data points, producing two error measures: one quantifying the inconsistency of the embedding with respect to the cell phase and the other with the cell type. For methods that provide a single embedding of the data, we average these two scores, quantifying how much this embedding is consistent with both latent processes. For methods that produce two embeddings, we expect each embedding to be consistent with only one of the latent processes. Therefore, in such cases, we assign to each embedding only one of its two scores (without repetition) such that the average of the assigned scores is minimized for the two embeddings.\n\nFor the rotating figurines dataset in Appendix D, each image is determined by three latent variables, the rotation angles of the three figurines. To compute an error measure for a given embedding of the dataset, we do the following. For each data point i and for each one of the three rotation angles, we find the k nearest neighbors of point i and the k nearest angles of angle i, and compute the relative set difference between the two groups. This provides three scores of angle inconsistencies for each point (corresponding to the angles). The rest of the procedure to compute the final error measure is analogous to the case of the biological data described above.\n\nFor each dataset, we computed the error measure for seven different methods: 1) t-SNE embedding using all features; 2) two t-SNE embeddings based on our partitions (‘tSNE FP’); 3) two embeddings of IC-PML; 4) a single embedding of LDLE; 5) two embeddings of Multi-tsne; 6) raw data features; and 7) raw data features after partitioning (‘FP’). For each method, we computed the error measure using different numbers of k nearest neighbors, where k = 2,4,6,...,50, resulting in a graph of the error measure as a function of k. \n\nThe resulting performance graphs can be found in anonymous.4open.science/r/FP-70F4. It is evident that for both datasets, our proposed partitioning provides the smallest error measure across all values of k, either after the embedding with t-SNE or using the raw features. We highlight that for IC-PML, Multi-tsne, and LDLE, we tested a wide range of hyperparameter values and retained the configuration that provided the smallest error measure for each k. Details are provided in the link.\n\n[A] He et al., Product manifold learning with independent coordinate selection.\n\n[B] Kohli et al., Low distortion local eigenmaps\n\n[C] van der Maarten and Hinton, Visualizing non-metric similarities in multiple maps\n\nQ2. Could you summarize and highlight the approximation quality of the proposed algorithm in the main paper?\n\nResponse. First, we would like to emphasize that our proposed algorithm (see Algorithm 1) does provide a solution to the hard partitioning problem (Problem 3.3). The next paragraph should make it clear.\n\nWe now clarify the rationale behind our algorithm and its derivation. The analysis of our proposed optimization problem in Section 3 suggests a natural alternating minimization strategy, by alternating between minimizing the objective function over the graph parameters and minimizing over the feature partitions (see Eqs. (9)–(11)). Unfortunately, due to the binary nature of the feature partitions, this procedure is sensitive to the presence of local minima. To address this issue, we introduce a regularized variant of the objective function (see Problem C.1 in Appendix C) that produces a soft assignment of features instead of hard assignments into partitions. Our proposed algorithm solves several instances of the regularized optimization problem sequentially, each one with a reduced regularization parameter. In the final step, the regularization parameter reaches zero, hence effectively minimizing the exact unregularized problem. As demonstrated in Appendix C, this sequence of solutions to the regularized optimization problems is less likely to get stuck in a local minimum compared to solving the exact unregularized problem directly. To clarify this issue, we will add this explanation to the main text at the end of Section 3.", "claims_and_evidence": "There are three main claims that the paper tries to establish:\n\n* \"Our approach generalizes traditional embedding and visualization techniques, allowing them to learn multiple embeddings simultaneously\" This claim is supported by the empirical study in both experimental section and appendix.\n* \"We establish that if several independent or partially dependent manifolds are embedded in distinct feature subsets in high dimensional space, then our framework can reliably identify the correct subsets with theoretical guarantees.\" This claim is partially support by the objective function ( laplacian scores) as well as the theoretical analysis. However, in the proposed algorithm that finds the optimal solution of the objective function is an soft approximation of the underlying combinatorial assignment problem. The approximation quality is not prominently discussed, which undermines the \"reliably identify\" claim.\n* \"Finally, we demonstrate the effectiveness of our approach in extracting multiple low-dimensional structures and partially independent processes from both simulated and real data.\" This claim is partially supported by the partitioning experiment as well as the visualization experiment. However, there are no strong baselines used in the comparison, i.e., methods that also assume data consists of multiple manifold and performs DR/factorization accordingly. Without stronger baselines (see questions below), the effectiveness of the proposed approach in practice is difficult to assess.", "methods_and_evaluation_criteria": "* The proposed method is sensible. However, the approximation quality of the proposed algorithm is not clear in the main paper.\n* The experiment settings are also sensible, however, also miss strong baselines.", "theoretical_claims": "I didn't went through the proofs.", "experimental_designs_or_analyses": "As mentioned above there are no strong baselines used in the comparison, i.e., methods that also assume data consists of multiple manifold and performs DR/factorization accordingly. Without stronger baselines (see questions below), the effectiveness of the proposed approach in practice is difficult to assess. Possible baselines are:\n\n* He et al., Product manifold learning with independent coordinate selection.\n* Kohli et al., Low distortion local eigenmaps\n* van der Maarten and Hinton, Visualizing non-metric similarities in multiple maps", "relation_to_broader_scientific_literature": "The idea of applying partition using by minimizing Laplacian scores of the assignments then visualization is interesting in the DR literature. I'm not familiar with the high dimensional feature partition literature, so cannot comment in that respect.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "The theoretical oriented approach is appreciated, as many DR papers (objective function + optimization) did not provide in depth theoretical analysis.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* Could you compare the proposed approach with stronger baseline mentioned above?\n* Could you summarize and highlight the approximation quality of the proposed algorithm in the main paper?", "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: This paper proposed to embed high-dimensional data via partitioning features using Laplacian smoothness optimization. It improves classical techniques and provides theoretical results of optimization and related asymptotic analysis. Reviewers praised that the proposed approach is origin, the paper is well written, and the theoretical results are supported with clear explanations and detailed proofs. Reviewers also raised concerns regarding the validation of the proposed work and the selected datasets. Authors’ responses to these concerns are satisfactory. Overall, this is a high-quality work, so the strong acceptance is recommended.
Decision: Accept (oral)