Geometric Analysis of Nonlinear Manifold Clustering
Authors: Nimita Shinde
Tianjiao Ding
Daniel Robinson
Rene Vidal
Venue: NeurIPS 2024 poster (2024)
Keywords: Manifold clustering
large scale clustering
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We provide a model for manifold clustering with theoretical guarantees

Abstract: Manifold clustering is an important problem in motion and video segmentation, natural image clustering, and other applications where high-dimensional data lie on multiple, low-dimensional, nonlinear manifolds. While current state-of-the-art methods on large-scale datasets such as CIFAR provide good empirical performance, they do not have any proof of theoretical correctness. In this work, we propose a method that clusters data belonging to a union of nonlinear manifolds. Furthermore, for a given input data sample $y$ belonging to the $l$th manifold $\mathcal{M}_l$, we provide geometric conditions that guarantee a manifold-preserving representation of $y$ can be recovered from the solution to the proposed model. The geometric conditions require that (i) $\mathcal{M}_l$ is well-sampled in the neighborhood of $y$, with the sampling density given as a function of the curvature, and (ii) $\mathcal{M}_l$ is sufficiently separated from the other manifolds. In addition to providing proof of correctness in this setting, a numerical comparison with state-of-the-art methods on CIFAR datasets shows that our method performs competitively although marginally worse than methods without

Geometric Analysis of Nonlinear Manifold Clustering
Nimita Shinde" Lehigh University
Tianjiao Ding" University of Pennsylvania tjdingäupenn.en edu
nis6230lehigh.c
Daniel P. Robinson
René Vidal
Lehigh University
University of Pennsylvania vidalr@upenn. edu
daniel. www..ooooononniiggg......... edu
Abstract
Manifold clustering is an important problem in motion and video segmentation, natural image clustering, and other applications where high-dimensional data lie on multiple, low-dimensional, nonlinear manifolds. While current state-of- the-art methods on large-scale datasets such as CIFAR provide good empirical performance, they do not have any proof of theoretical correctness. In this work, we propose a method that clusters data belonging to union of nonlinear manifolds. Furthermore, for given input data sample belonging to the (th manifold Mr, we provide geometric conditions that guarantee a manifold-preservingg representation of be recovered from the solution to the proposed model. The geometric conditions require that (i) Mi is well-sampled in the neighborhood of y. with the sampling density given function of the curvature, and (ii) Mi is sufficiently separated from the other manifolds. In addition to providing proof of correctness in this setting, numerical comparison with state-of-the-art methods CIFAR datasets shows that our method performs competitively although marginally worse than methods without theoretical guarantees.
Introduction
Manifold clustering is fundamental problem in data science, in which seeks to cluster data
lying close to a union of low-dimensional manifolds. It has vast number of applications, such as
clustering image pixels [13,, ii) video frames [ iii) images of faces (6), hand-written digits [7]
or other natural objects [8], iv) rigid-body motions 9 v) human actions [1012), and vi) searching
policies for robots 113 name few.
Over the past two decades, there has been a considerable amount of work on subspace clustering, the special case where each manifold is linear or affine subspace. A key to the success of many of these works can be attributed to the idea of self-expressiveness [14] one can write a data point as linear (or affine) combinations of other points, i.c., given data point and matrix of data points X, holds that y = Xe for some vector c. The observation that the support of the sparsest such should correspond to data points in the same subspace prompted the study of the optimization problem
min r(c) + IlellB subject to (s.t.) e e Xc,
(SC)
where r(-) is a regularizer on (e.g.. 11- to promote sparsity balances the two terms in the objective. By solving an instance of (SC) for each point in the dataset, one obtains one coefficient vector per point, and the matrix of all coefficients for all points can be
and À is a parameter that
These authors contributed equally to this work
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

used to build similarity graph of the points and run spectral clustering to obtain a clustering of the data. This has spurred fruitful line of research, leading to various formulations based on different and theoretical guarantees on having the
regularizers [6 20). efficient algorithms 18
21 22
correct support 23
While many interesting datasets (nearly) satisfy the linear or affine subspace assumption, there are a variety of tasks with associated datasets that grossly violate it. For example, natural image datasets such as CIFAR [33 and ImageNet [ cannot be well modeled by low-dimensional subspaces. Instead, it is more natural to assume that each cluster modeled by a smooth diw-dimessioal non- linear manifold, more general case of manifold clustering. Notably, this is much more challenging than subspace clustering, as the global linear relationship among points in each subspace absent.
Although a few nonlinear manifold clustering methods have achieved high clustering accuracy on large-scale datasets, they lack theoretical justification. For example, the work in (55533 aims to learn an embedding (or kernel) via neural networks with subspace clustering style loss functions on the embedded data. While these methods have progressively improved the state-of-the-art in clustering performance, with the most recent ones achieving over 89% accuracy on CIFAR-10 10 [54]-
[56], little is theoretically understood about why these methods work. In fact, the work of [57 argues the opposite, that some of these methods are provably ill-formulated and learn trivial embeddings
The current paper provides an approach that is both theoretically grounded and empirically tested on modern large-scale datasets. An interesting method that motivates us is sparse manifold clustering and embedding (SMCE) [58]. It views local neighborhood of a manifold approximately dimensional affine subspace, and solves a modified version of (SC) that reweights data and adds an affine constraint 1 c = 1. Despite its effectiveness on simpler datasets such Extended Yale-B (59), COIL20 [60], and MNIST [7] as observed by [61), so far there is no theoretical understanding of when this method will succeed, nor has it been applied to large-scale datasets.
low-
Nevertheless, the method SMCE inspires our work. A major difficulty in providing theoretical guarantees for SMCE is to deal with the affine constraint. This motivates us to relax the constraint as a penalization, leading to the following model based on the self- expresssresssss of the input sample y:
A min W + =/ [|le|2 + (1 17-) 2
= y- Xc,
(1.1)
where W is a diagonal matrix with j-th diagonal entry wy an increasing function of the Euclidean distance between y and data sample x. The regularizer [|Well, Well was adopted from SMCE to promote sparse solutions with support determined by "close" data points. Comparing (I.) with (SC). we see two differences: (i) (I.I) replaces r(c) with new regularizer that is a function of and W. and (ii) (I.I) penalizes violation of the constraint 1 T in the objective by introducing the term (1 - 1 1Teja. Thus, as 1) goes to infinity, the data sample will be represented by an affine combination
of input data samples. It then natural to ask the following question:
Question 1. Can we provide geometric conditions based on the input data samples and structure of the undertying manifolds that ensure that every optimal solution to (I.I) is manifold preserving, i.e.,
the non-zero entries of an optimal solution correspond to data from the same manifold as y?
1.1 Contributions
In this paper, we propose model that generates an approximately affine representation of an input data sample and provide an answer to Question 1. Our contributions are summarized below.
We propose to perform manifold clustering via the convex optimization problem (I.I. which is based on self-expressiveness property. Notably, the proposed formulation can be efficiently solved using fast active-set-basee method. We then construct an affinity matrix based on the solutions to 1.1p and then use spectral clustering to cluster the data.
Formulation:
Theory: Using our new formulation, we provide an answer to Question Tb giving theoretical guarantees for any optimal solution of (I.I] to be manifold preserving (see Definition IT. The results depend on the curvature of the manifold at y, the relative location of the data samples in the neighborhood of y. i.e., the distribution of the sample in the neighborhood, and the separation between the samples from other manifolds and the neighborhood of y.
Accuracy and running time of methods with theoretical guarantees of correctness have been reported on only datasets with small number of samples clusters, low ambient dimension; see Appendix C review.

---

Experiments: We compare the performance of the proposed method with state-of-the tfe-----ttt--tttt alternatives on CIFAR-10,-20 10,-20 and -100 datasets. The proposed method performs consistently better than subspace clustering methods, and only marginally worse than methods based on deep networks.
1.2 Notations
For l = 1, 1,..., Tu, we let Mi denote nonlinear manifold in R.D with intrinsic dimension di & D. We define M = M y to be the union of manifolds. Let N data samples be generated from M, which we represent as the columns of X [i.....,2y: E RDx, Additionally, let y be assume that y E M₁, Furthermore, for I,..., L, let M, denote the set of generated input data samples that lie on Mr, and define M = Uf= M, to be the set of all N data samples. For given subspace S, we let (2( denote the orthogonal projection of r onto the subspace S.
new generated from the union of manifolds M. Without loss of generality,
Outline. In Section we introduce our proposed model, define key quantities used in the analysis, and provide theoretical results for the proposed model. In Section 3 we perform experiments on synthetic data aimed to improve our understanding of the theoretical results, followed by a comparison with other existing methods real data. We conclude the paper in Section
Proposed Model and Theoretical Analysis
The model [.I] we study is obtained by penalizing the affine constraint 1 1dc = in SMCE (58) with
penalty parameter 1j. The penalty term in the model (T.I is equivalent to homogenizing the data samples with homogenization constant vT). Thus, we we propose to study the equivalent problem
min ||Wella + 2 1TE s.t. z= -c
(WMC)
where À > O, W is a diagonal matrix with positive entries that depend on the Euclidean distances between y and the input data samples, X E (D+1)xN is the matrix whose j-th column, Zj. the homogenized data sample (ar7" vT)" with v) > a chosen constant, and y == (v" vn)". One could define wy == Wjj = ||ar /ll2/ (E -| yll2), although other reasonable choices are possible.
2.1 Definitions and assumptions
In this section, we state our assumptions and define key quantities used the theoretical results. Our theoretical analysis provides an answer to Question i.e., we provide conditions under which the non-zero entries of a solution ex (WMC) correspond to data samples from the same manifold as y. If e satisfies this property, it is called a manifold preserving solution, as we now define.
Definition (Manifold preserving). For the data sample .M,, we say that the optimal solution c" to WMCC is manifold preserving if and only if of = 0 for all x, & M..
If one considers solving N instances of problem (WCC) (each instance is defined by replacing y with Ty. and removing æj from X). then the N solutions may be used to define similarity graph. If the solution to each instance manifold preserving, then the similarity graph will only have intra-cluster connections (no iiterrcuuttrrffalee connections). Consequently, it would be expected that applying spectral clustering to such graph will result in correct clustering of the data.
We now introduce key quantities and assumptions required to prove the results in Sections 2.2 and 2.3
i.e., to derive conditions under which any optimal solution to (WMC) is manifold preserving.
We assume that each manifold is smooth and the input data samples generated on each manifold are noiseless. Furthermore, we assume that at least di + 2 samples are generated on each manifold My where we recall that d₃ the intrinsic dimension of manifold Mi.
Assumption 1.
Definition 2 (Set of nearest neighbors N). For the data sample y E MM. define B to the D- dimensional ball of smallest rudius centered at such that it contains d1 +1 points from M,, where d the dimension of manifold M1. Define N be the set of all data samples B excluding y. and note that N may contain samples from both M1 and Uf M,.
3

---

Definition 3 (Nearest affine subspace S). For the data sample M1 and N in Definition 2 define the nearest affine subspace, as the affine subspace generated by the set N O M,, i.e.
we
= aff : 2y E ENOM)))
(2.1)
Furthermore, we define == span zij homogenized data samples from the set N
NiMM as the linear subspace spanned by the
M..
Assumption 2. For the affine subspace S defined in Definition we assume that dim(S) d1- Equivalently, we assume that dim(S) = d1 + 1.
The affine subspace S spanned by the d1 + points
nearest to on the manifold M₁ (see Figure [ for illustration when M one-dimensional) We can view S as approximation of the tangent space to M at
M2
C4
We now define the dual of (WMC) since our analysis requires knowledge of the dual variables.
3
B
y
Definition 4 (Weighted & norm and its dual). The dual norm of the weighted & norm ||e||,, = [[el]h is
T2
S
Mi
max lgp1 JE[N] Wj
max [|
====
(2.2)
We can write the dual of WMC as
2x s.t.
IX oloo,w--1 1.
Figure I: The affine space S approxi- mates the tangent the I-dimensional manifold Mi at y. Observe that {o, C N and that f21, C M1
VER
(2.3)
The constraint in 2.3 can be equivalently written as
(zzj, u\| Wy for all 1 N.
(2.4)
We now define two more quantities (Definitions 5 and 6 that appear in our main results (see Lemma and and Lemma B. Remark[[aass gives additional insight these quantities.
Definition (Dual direction). For the data sample E M1, define X as the matrix with columns that span the linear subspace S in Definition 3 ie., X [Tyle] Define the reduced problem
min [|e]l. + b X scll2
(2.5)
and its corresponding dual
max
T v)
2X
1
s.t.
1X S 1.
(2.6)
Then, we define the dual direction v² as the unique optimal solution to (.6).
The dual direction D* is used to define the separation between the manifold M and other manifolds.
We elaborate on this in Remark
Definition (Inradius r(Q5) )). For the data sample y E MM, define
{ Fj {
W Q
ENOM
conv
(2.7)
Wi
We define r(Q's W Eaclidean ball contained in Q3 For simplicity, we use the notation, w rr(Q's
as the inradius of the symmetric convex body Q W i.e., the radius of the largest
It follows from Definition that the inradius W increases as {wj} decrease. Since {wy} are proportional to the distances between y and the d, + points closest to y in the set M,, the inradius increases when more samples generated from Mi y (see Remark I for more details).

---

2.2
general geometric conditions
Our first theoretical result provides geometric conditions that ensure that an optimal solution of (WMC). defined for given imput data sample is manifold preserving (see Definition
Lemma 1. For y E My, input data X, and X > 0, define the model (WMC) and Assumptions
and 2 hold. Let S and S be defined as in Definition 3 and v² and r be as given in Definitions and 6 respectively. Let dist(y.S) S) be the Euclidean distance between and subspace S, and define
Wkr Ker.Pst
(x "
min axEM,M
The following statements hold.
(a) If
7" > 0 and
(2.8)
y
dist(y, S) < |77|2
(2.9)
+ W
then the interval (M := (FW( 7 disty.sT]
is well defined and nonempty.
(b) If X E ("), then every optimal solution to @MC is manifold preserving and nonzero.
To help the reader better under the inequalities in 2.8 and
2.9
we give the following remark.
Remark For the d1 dimdeensionnal manifold M1. conditions
2.8 and (2.9 depend on the following:
1. Inradius , ,.W (see Definition 6 provides information of the distribution of the d1 closest data samples to on the manifold M1, i.e., the samples belonging to the set M1 N.. The inequalities in (2.8) and (2.9) are more easily satisfied if w increases. From the definition of the inradius rW, it is clear that increases when the samples in the set M, nn are more uniformly distributed. Furthermore, suppose we generale more samples from the manifold M1 near y. Then, the distances of the d1 + 1 samples in the set M2 n N from will decrease, resulting in a larger inradius. Thus, W increases when either the number of samples generated from the manifold M2 near y increases or the samples in the set M, n N are well-distributed
2. Inner product (v=))) For each In E M. M,, the inner product defines the separation between IV and the subspace S. If the separation between each point In E M M, and S increases, the inner product decreases. From the definition o W, it is clear that the inequalities in (2.8) and 2.9h are more easily satisfied when the separation increases.
Part (a) of Lemma D provides conditions (based on the separation of samples belonging to other manifolds from S, as well as the distribution of the input data samples in the neighborhood of y) for the interval (X (")
(") to be nonempty. Note that X' is function of and X while A" is a function y, X, and À since 7 depends on v², which is an optimal solution (2.6) with parameter A.
Part (b) of Lemma| states that if the hyperparameter À satisfies X' < A < A", then every solution choose À (y, X), to explicitly compute À satisfying < A" (when such a value exists) requires defining A function of X. Although Lemma ① does not provide this relationship. numerical experiments in Section 3.1 on randomly generated data clarify how X' and X change as a function of (y, X) and X.
to (WMC) is manifold preserving and nonzero. While
>>>> X based on knowledge of
Interestingly, geometric result in (62) for a linear subspace model can be recovered from Lemma Corollary 1 (Special case of (WMC)). For y E MM, input data X, and X > O, define the model (WMC) with W T. Assume that || = =|=,112 1 for each data sample F.j, and that Assumptions and hold. in addition to the quantities defined in Lemma | define
Px(")) [PP{(v))) 112
# M.MM,,
max
and let r r= w = = since W T. then follows from Lemmal 7 hat if
and distly, S) Itr-p
(2.10)
5

---

then the interval ((I-distt.,s)) interval, then every optimal solution to (WMC) is manifold preserving and nonzero.
p- is well defined and nonempty. Moreover, if is this rdl
Furthermore, if the manifolds linear, then dist(y, S) since y E S. Thus, in this special case, if < r, then for any X > L/r, every optimal solution to (WCC) is subspace preserving and nonzero.
2.3 Manifold-preservinngg curvature-based geometric conditions
Although believe the results in the previous section the first of its kind, they depend on quantities related to projections onto S, which we would like to avoid, if possible. To achieve this goal, we require curvature information of the manifold Mj as well as the reach of the manifold M1- Let us define the curvature and the reach of manifold.
Definition 7 (Curvature of a manifold). Let M1 be a smooth manifold with y E MM 1f1/K is the radius of the largest (internal) tangent circle to M1 at y, then the curvature of Mi at y is K.
Definition 8 (Reach of manifold). Let M1 be smooth manifold. The reach of the manifold M1. (1), is the largest value such that for any x & M1 and dist(z, MM1 S. reach( M1). x has a unique projection onto M1. If is the curvature of the manifold M1. then reach(M1) 1/k.
In Figure I. x denotes the curvature of the I-dimensional manifold M₁ at y. The curvature of the manifold at gives bound on how fast the direction of point the manifold changes with respect to the distance traveled. The larger the change in the direction (or the angle), the larger will be the curvature. For linear manifolds, the curvature is zero
In Lemma 2 we give a relationship between the curvature of the manifold Mi at y, the radius the ball B centered at and dist(y, S). Then, in Lemma 3 we provide geometric conditions based on curvature that guarantee that any optimal solution of (WMC) manifold preserving.
Lemma 2. Let Assumptions [and For y Mi, let B and S be as defined in Definitions 2 and 3
respectively. Let Ç ((B) be the radius of the sphere B, k be the curvature of the manifold MI at
reach(M1) be the reach of the manifold M1. and dist(y, S) be the Euclidean distance between and the subspace S. If reach(M,) 2 S, then
1
dist(y, S)
-2.
(2.11)
Combining Lemma I and Lemma 2 gives our final result.
Lemma 3. For y E Mr, input data X, and X > O, define the model (WCC) and let Assumptions 7 In addition to the quantities defined in Lemmal) [ let be the radius of the sphere B,
be the curvature of the manifold Mi at y, and reach(Mi) be the reach of the manifold Mi. The following then hold.
(a) If
w" 0,
(2.12)
reach(Mi) 2 C,
and
(2.13)
1
w + w
52
|1013
(2.14)
K
R2
then there exists non-empty interval (2,24) :=
W
WW
(1
w
(b) E ("), then every optimal solution to (WCC) is manifold preserving and nonzero.
The quantity " in Lemma captures the notion of distribution of the data samples in the set M1 N as well as separation of the data samples not in M, from S. The condition (2.12) requires w to be positive. Condition (2.13) is related to the sampling density of the manifold Mi near y. the number of samples generated on Mi near y increases, then ( will decrease. Meanwhile, if the curvature x of the manifold at y large, 1/1 will be small, and from Definition X we see that reach(M1) will be small. This indicates that for (2.13 to hold, one may need to generate more samples on Mi near

---

provides lower bound on 7h based on s (the curvature) and Ç (the number of samples generated on M near y). When all three of these conditions hold, we have a non-empty interval (X' X²) as defined in Lemma aa). If X < À < X", then Lemma 3 ()) ensures that every optimal solution (WMC) manifold preserving and nonzero.
Finally, (2.14)
3 Computational Results
In this section, we first perform experiments on randomly generated data to understand how the quantities in Lemma[ tion 3.Tp. Next, in Subsection 3.2 we compare the performance of our model (WMC) with existing methods on CIFAR datasets. Our goal here is to check the performance of (WMC) and to show that while (WMC) does not outperform the state-of-the-art methods, performs only slightly worse in terms of clustering accuracy.
function of the input data and the hyperparameter À (see Subsec-
3.1 Experiments on synthetic data and understanding Lemma 1
In this section, we perform two experiments designed to understand how X' and X (see Lemma 1 change function of the number of data samples N and hyperparameter À for randomly generated data from two trefoil knots. The noiseless data samples are embedded in 1000 The embedding of data involves generating random orthonormal basis of a subspace in 1000 followed by projecting the samples generated from two trefoil knots onto this subspace. We choose ij 1 and define the
matrix W as a diagonal matrix with j-th diagonal entry w/ lly xz /2/l2// Σσ by xx|12- 12-
Experiment 1: {X, >"} versus X. For this experiment, we evaluate how the values X and A change when only À changes. We generate N1 E {120, 150, 160, 200} and N2₂ 40 data samples from two non-intersecting trefoil knots of intrinsic dimension d1 = dg 1. We generate 50 different random embeddings of the data samples from the trefoil knots in R 100 We plot the mean values and standard deviations X' and X" for different values of À E [4.8, 204.8] x 10-4 in Figure
Since X' is independent of X. its value is constant for all values of N2). It also appears that A is monotonically increasing function of À that eventually reaches "steady-state" value. When N1 120, we observe that the conditions Lemma aa) are not satisfied for any value of and that the interval (X', A²) is empty. When N₂ = 150, we observe that A" > X for À > 0.0012, but for these X values it also holds that À > A", meaning that Lemma ( is violated for all X > When N1 E {160, 200), we observe that for some values of X > 0, there exist non-empty intervals (X', A²) such that À E (A)) every optimal solution (WCC) is manifold preserving and nonzero. We can conclude from these experiments that for certain input data X). there exists range of acceptable values of X for which the conditions defined in both parts (a) and (b) of Lemma] T are satisfied, so that every optimal
A²). Thus, for every such X E (X', A²), it follows from Lemma that
solution to (WMC) is nonzero and manifold preserving.
120, 40
=100 4,=40
160, 4,=
Ni =200, N₂=40
0.000
0.000
0.000
0.005
0.000
-0.005
0.005
-0.005
-0.055
-0.010-
1
-0.010
-0.010
00.000
0.001
0.002
0.001
0.002
0.001
0.002
0,001
0,002
Figure 2: Plot X1 X", and for (N1, N₂) samples generated from two trefoil knots. The data generated from the knots are embedded in R 100 with 50 randomly generated embeddings.
Experiment 2: (*) versus N. In this experiment, we aim to understand how X² and X change when the number of data samples, N, changes. We let N, = N₂ and gradually increase N = N₁ + N2. We generate 50 different random embeddings of data samples from trefoil knots
7

---

in R 100, For each pair of data (y, X), we compute X and then create three values for À by setting = ax for a E {2, 5, 50). Then, for each À value, we plot X and A versus = Nı + N₂ in Figure We can observe that as the number of samples increases, the size of the interval (X X")
increases linearly.
We further observe that for a the interval (*) non-empty (satisfying the conditions in Lemma aa) for all N > 890, whereas for a 5, 50, the interval is non-empty for all N > 300. Thus, we see that the small value of a leads to slower increase X resulting the interval (X² A*)
becoming non-empty at much larger value of N. Furthermore, we also see that, (i) when a = 5.
E (X', X²) ) for all 2 330, and (ii) when a = 50, À E x*) for all 2 510. In other words.
when = 5, the conditions in both parts (a) and (b) of Lemma are satisfied for all N 2 330,
whereas when a = 50, the conditions in parts (a) and (b) of Lemma are satisfied for all N 2 510,
making À 5X', the best choice of the hyperparameter in this experiment.
A 2=
A= 2-
==50-
0.002
0.02
0.04
0.000
0.01
0.02
-0.002-
A
2
0.00
-0.004
0.00
500 N
1000
500 NV
1000
500
1000
N
Figure 3: Plot of A A and N = N2+ with N; = N2 and À = ax for a E (2, 5, 50}. Samples generated from two trefoil knots and embedded in 100 with 50 randomly generated embeddings.
3.2 Experiments on real data
In this section, we compare the empirical performance of our model with existing methods on CIFAR-IO, CIFAR-20,, CIFAR-I00 datasets (33). The CIFAR dataset consists of 60000 color images of size 32x that are divided into 10, 20, and 100 classes for CIFAR-10, CIFAR-20, CIFAR-108 respectively. In Section 3.2.1 we describe the steps for clustering data using our model (WMC). followed by a comparison of empirical results in Section 3.2.2
(See Appendix B. for more details.)
3.2.1 Clustering data using (WCC)
We follow the steps in Algorithm 1 to cluster the input images using our model (WMC.
Algorithm Pseudocode for clustering data using (WMC)
Input: Images from CIFAR dataset, À >> 0, and the number of clusters T.
1: Generate features using the CLIP encoder [63].
2: Construct a representation matrix C by solving problem (WMC) for the CLIP feature vector for each input image.
3: Construct a symmetric affinity matrix A from C.
4: Apply spectral clustering A to get the L clusters.
Output: clusters of data
The CLIP (Contrastive Language-Image Pre-Traine Pre-Training) 633 encoder is a powerful tool in pre-training data. Given its prior success, we use CLIP to map each input image in CIFAR to a feature vector in Step of Algorithm T Step 2 of Algorithm emmploys our model|WM[Cee construct a representation matrix C. We now briefly explain this step. For the feature vector of each input image: (a) we define the positive diagonal distance matrix W so that each diagonal entry an increasing function of the Euclidean distance between y and each of the other feature vectors, (b) we define the
model (WC)) for À > 0, (c) we solve (WMC) using an active-set method [88] to (hopefully) obtain manifold preserving representation for the feature vector of each input image. (The choice of À and W explained further Subsection 3.2.2) Similar to classical spectral clustering methods, the representation matrix is used to define symmetric affinity matrix A; here, we choose A

---

Table Comparing clustering accuracy (ACC) and Normalized Mutual Information (NMI) for our models L-WMC and E- E-WMC with state-of-the art subspace clustering and deep clustering methods. Each method is used cluster the data pre-trained using CLIP [63. For each metric (ACC and NMI) and data set, the best overall value achieved is bolded, and the best value achieved by our method is blue.
Dataset
CIFAR-I0
CIFAR-20
CIFAR-100 ACC
Metrics
ACC NMI
ACC
NMI
NMI
Methods that do not fine-tune representations
L-WMC 96.07
90.54
63.97
69.55
69.2
76.49
E-WMC 94.34
88.79
64.1
69.58
69.83
76.63
SMCE
86.86
90.66
63.1
70.53
68.56
77.17
EnSC 18
85.8
89.2
61.6
69.3
66.6
77.1
SSC 22
85.4
84.6
60.9
65.3
64.6
72.8
Methods that fine-ture representations
TEMI 64 +
96.9
92.6
61.8
64.5
73.7
79.9
CPP 56
97.4
93.6
64.2
72.5
74.0
81.8
"The numerical results in this row are taken from [56].
See appendix
[6 for details on fine-tuning models.
EICI| + |CIT). (We used this definition in combination with other techniques to construct A, which explained in detail in Appendix B.2 Finally, use spectral clustering A to cluster the data.
Output metries. We use two metrics to compare the performance of various clustering methods. In particular, we use Clustering Accuracy and Normalized Mutual Information whose values range from 0 to 100%, with higher values indicating better performance.
3.2.2 Numerical Results
In this section, we compare the numerical performance two instances of our Algorithm D with the subspace clustering methods (a) Elastic Net Subspace Clustering (EnSC) [18] and (b) Sparse Subspace Clustering, manifold clustering method (c) SMCE (58), and with the deep clustering methods (d) CPP (56] and (e) TEMI (64). Each method is applied to the CLIIP features extracted from
the input images. The two instances of our Algorithm are determined by how the weight matrix W chosen in (WCC),
now deseribe.
L-WMC: Linearly Weighted Manifold Clustering model with wy | y/12/ Σx || y/1a for all j in (WMC). Here, the weights {wy} } are linearly proportional to the Euclidean distances.
E-WMC: Exponentially Weighted Manifold Clustering model with weights in (WMC) defined as wy = exp(2| vll2)/ Σe exp(21|<ra v/l2) for all j. Here, the weights {wy are defined an exponential function of the Euclidean distances.
We report the clustering results for L- and E-WMC in Table I (See Appendix B. for details on the choice of and 17.) From Table we can observe that the clustering accuracy of L-MC and E-WMC is consistently better than EnSC, SSC and SMCE for all three datasets. Moreover, L-WMCC and WMC perform slightly worse than the state-of-the-ae method CPP on the CIFAR-10 and CIFAR-20 datasets. So, although our method does not outperform the existing state-of-theaae art method, our method the first to perform similarly to the state-of-the-aa methods and have a theoretical guarantee of correctness (see Lemma I and Lemma 3)
4 Discussion
In this paper, propose model whose solution defines a self-expressive representation of the input data, and provide a theoretical analysis correctness of the model (see Lemma [ and Lemma For data X)) and hyperparameter X > 0, give conditions under which the solution model is

---

non-trivial and manifold preserving. To the best of our knowledge, this is the first work that provides a theoretical understanding of manifold clustering models. We also show that our model performs only marginally worse than the current state-of-the-ne methods on CIFAR datasets.
For given data set, our analysis does not provide strategy for choosing the hyperparameter À 0 so that it satisfies the conditions in Lemmal I This leads to an important open question: For any given data set, can one provide a proof of existence of X 0 for which the conditions in Lemmal [ are satisfied? If so, can one provide a closed form expression to choose the value of X? An answer to this question will result an "optimal" choice for the value of X, thus avoiding the cost of tuning
Acknowledgements
We would like to thank the generous support provided by the National Science Foundation's through grants 1704458, 203 1985 and 2212457, and the Lehigh internal grant funding the project "Founda- tions and Applications of Mathematical Optimization and Data Science".
References
[1] Yi Ma, Harm Derksen, Wei Hong, and John Wright. Segmentation of multivariate mixed data via lossy data coding and compression. IEEE transactions on pattern analysis and machine intelligence, 29(9): 1546-1562, 2007.
[2] Cheolkon Jung, LC Jiao, Juan Liu, and Yanbo Shen. Image segmentation via manifold spectral clustering. 2011 IEEE International Workshop on Machine Learning for Signal Processing, pages 1-6. IEEE, 2011.
[3] Li Liu, Liang Kuang, Yunfeng Ji, et al. Multimodal mri brain tumor image segmentation using sparse subspace clustering algorithm. Computational and Mathematical Methods in Medicine, 2020, 2020.
[4] Stephen Tiemny, Junbin Gao, and Yi Guo. Subspace clustering for sequential data. In Proceed- ings of the IEEE conference on computer vision and pattern recognition, pages 1019-10266 2014.
[5] Sheng Li, Kang Li, and Yun Fu. Temporal subspace clustering for human motion segmentation. In Proceedings of the IEEE international conference computer vision, pages 4453-4461, 2015.
[6] Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and appli- cations. IEEE transactions on pattern analysis and machine intelligence, 35(11):2765-778) 2013.
[7] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11))2278-2224 1998.
[8] Zengyi Li, Yubei Chen, Yann LeCun, and Friedrich Sommer. Neural manifold clustering and embedding, arXiv preprint arXiv:2211.1000) 2022.
[9] Alvina Goh and René Vidal. Segmenting motions of different types by unsupervised manifold clustering. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-6. IEEE, 2007.
[10] Fei Wu, Yongli Hu, Junbin Gao, Yanfeng Sun, and Baocai Yin. Ordered subspace clustering with block-diagonal priors. IEEE transactions on cybernetics, 46(12):3209-322 2015.
[11] Behnam Gholami and Vladimir Pavlovic. Probabilistic temporal subspace clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3066-3075, 2017.
[12] Giancarlo Paoletti, Jacopo Cavazza, Cigdem Beyan, and Alessio Del Bue. Subspace clustering for action recognition with covariance representations and temporal pruning. 2020 25th International Conference on Pattern Recognition (ICPR), pages 6035-6042. IEEE, 2021.
10

---

[13] Rafael Garcia, Bruno C da Silva, and João LD Comba. Task-based behavior generalization via manifold clustering. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 6047-6052. IEEE, 2017.
[14] Ehsan Elhamifar and Rene Vidal. Sparse subspace clustering. pages 2790-2797, June 2009.
[15] Can-Y Yi Lu, Hai Min, Zhong- -inngQQiuu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. In Computer ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part VII 12, pages 347-360. Springer, 2012.
[16] Guangean Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, and Yi Ma. Robust recovery of subspace structures by low-rank representation. IEEE trunsactions pattern analysis and machine intelligence, 35()):171-184, 2012.
[17] Reinhard Heckel and Helmut Bölcskei. Robust subspace clustering via thresholding, IEEE Transactions on Information Theory. 61(11))6320 6342, 2015.
[18] Chong You, Chun-Guand Li, Daniel P Robinson, and René Vidal. Oracle based active set algorithm for scalable elastic net subspace clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3928-3937, 2016.
[19] John Lipor, David Hong, Yan Shuo Tan, and Laura Balzano. Subspace clustering using ensembles of k-subspaces. Information and Inference: A Journal of the IMA, 10(1):73-107, 2021.
[20] Connor Lane, Ron Boger, Chong You, Manolis Tsakiris, Benjamin Haeffele, and Rene Vidal. Classifying and comparing approaches to subspace clustering with missing data. In Proceedings of the IEEF/CVF International Conference on Computer Vision Workshops, pages 0-0, 2019.
[21] Yanxi Chen, Gen Li, and Yuantao Gu. Active orthogonal matching pursuit for sparse subspace clustering. IEEE Signal Processing Letters, 25(2):164-168, 2017.
[22] Chong You, Daniel Robinson, and René Vidal. Scalable sparse subspace clustering by orthogo- nal matching pursuit. In Proceedings of the IEEE conference computer vision and pattern recognition, pages
2016.
[23] Manolis Tsakiris and Rene Vidal. Theoretical analysis of sparse subspace clustering with missing entries. In International Conference on Machine Learning, pages 4975-4984. PMLR, 2018.
[24] Chhn-Guann Li, Chong You, and René Vidal. On geometric analysis of affine sparse subspace clustering. JEEE Journal of Selected Topics in Signal Processing, 12(6):1520-15 1533, 2018.
[25] Mahdi Soltanolkotabi and Emmanuel J Candes. A geometric analysis of subspace clustering with outliers. 2012.
[26] Mahdi Soltanolkotabi, Ehsan Elhamifar, and Emmanuel Candes. Robust subspace clustering. 2014.
[27] Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. Journal of Machine Learning Research, 17(12): 2016.
[28] Yining Wang, Yu-Xiang Wang, and Aarti Singh. A deterministic analysis of noisy sparse subspace clustering for dimensionallty-reduee data. In International Conference on Machine Learning, pages 1422-1431. PMLR, 2015.
[29] Daniel P Robinson, Rene Vidal, and Chong You. Basis pursuit and orthogonal matching pursuit for subspace-preserving recovery: Theoretical analysis. arXiv preprint arXiv: /3091, 2019.
[30] Chong You, Chun-Guang Li, Daniel P Robinson, and René Vidal. Is an affine constraint needed for aftine subspace clustering? Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 9915-9924, 2019.
11

---

[31] Peng Wang, Huikang Liu, Anthony Man-Cho So, and Laura Balzano. Convergence and recovery guarantees of the k-subspaces method for subspace clustering. In International Conference on Machine Learning, pages 22884-2299 PMLR, 2022.
[32] Tianjiao Ding, Derek Lim, René Vidal, and Benjamin D Haeffele. Understanding doubly stochastic clustering. In International Conference on Machine Learning, pages 5153-5165. PMLR, 2022.
[33] Krizhevsky Alex. Learning multiple layers of features from tiny images. https://www. cs. toronto.
2000--r pdf. 2009.
[34] Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journn of computer vision, 1 115:211-253 2015.
[35] Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and Ian Reid. Deep subspace clustering networks. volume 2017- pages 24-33, 2017.
[36] Xi Peng. Jiashi Feng, Shijie Xiao, Jiwen Lu, Zhang Yi, and Shuicheng Yan. Deep Sparse Subspace Clustering. arXiv [cs. CVJ, September 2017.
[37] Mahdi Abavisani and Vishal M Patel. Deep Multimodal Subspace Clustering Networks. IEEE Journal of Selected Topics in Signal Processing, 12(6):10011611, April 2018.
[38] Yangbangyan Jiang. Zhiyong Yang. Qianqian Xu, Xiaochun Cao, and Qingming Huang. When to Learn What: Deep Cognitive Subspace Clustering. In Proceedings of the 26th ACM interna- tional conference Multimedia, MM '18, pages 718-726, New York, NY, USA, October 2018. Association for Computing Machinery.
[39] Xi Peng, Jiashi Feng, Shijie Xiao, Wei- Yun Yau, Joey Tianyi Zhou, and Songfan Yang. Structured AutoEncoders for Subspace Clustering. IEEE Transactions Image Process- ing, 27(10):5066-008, October 2018. Publisher: IEFE.
[40] Xiaoliang Tang, Xuan Tang, Wanli Wang. Li Fang, and Xian Wei. Deep Multi-view Sparse Subspace Clustering. In Proceedings of the 2018 VII International Conference Network, Communication and Computing, ICNCC 18, pages 115-119, New York, NY, USA, December 2018. Association for Computing Machinery.
[41] Pan Zhou, Yunqing Hou, and Jiashi Feng. Deep adversarial subspace clustering. In 2018 IEEE/CVF conference on computer vision and pattern recognition, pages 1596-1604, 2018.
[42] Yangbangyan Jiang, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. Duet robust deep subspace clustering. In Proceedings of the 27th ACM international conference on multimedia, Mm 11,, pages 1596-1604, New York, NY, USA, 2019. Association for Computing Machinery. Number of pages: 9 Place: Nice, France.
[43] Ruihuang Li, Changqing Zhang, Huazhu Fu, Xi Peng, Joey Tianyi Zhou, and Qinghua Hu. Reciprocal Multi- Subspace Learning for Multi- Clustering. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 8171-8179, Scoul, Korea (South), October 2019. IEEE
[44] Xiukun Sun, Miaomiao Cheng, Chen Min, and Liping Jing. Self-Supervised Deep Multi- Subspace Clustering. In Proceedings of The Eleventh Asian Conference on Machine Learning. pages 1001-1016. PMLR, October 2019. ISSN: 2640-3498.
[45] Meng Zeng, Yaoming Cai, Xiaobo Liu, Zhihua Cai, and Xiang Li. Spectral-Spatice Clustering of Hyperspectral Image Based on Laplacian Regularized Deep Subspace Clustering. In IGARSS 2019 2019 IEEE International Geoscience and Remote Sensing Symposium, pages 2694-2697, July 2019. ISSN: 2153-7003.
[46] Meng Zeng, Yaoming Cai, Zhihua Cai, Xiaobo Liu, Peng Hu, and Junhua Ku. Unsupervised Hyperspectral Image Band Selection Based on Deep Subspace Clustering. IEEE Geoscience and Remote Sensing Letters, 16(12))188911888 December 2019. Conference Name: IEEE Geoscience and Remote Sensing Letters.
12

---

[47] Tong Zhang, Pan Ji, Mehrtash Harandi, Wenbing Huang, and Hongdong Li. Neural collaborative subspace clustering. 36th International Conference on Machine Learning, ICML 2019, 2019- June: 1777:12777- 2019.
[48] Junjian Zhang, Chun-Guang Li, Chong You, Xianbiao Qi, Honggang Zhang, Jun Guo, and Zhouchen Lin. Self-Supervised Convolutional Subspace Clustering Network. 2019.
[49] Lei Zhou, Xiao Bai, Dong Wang. Xianglong Liu, Jun Zhou, and Edwin Hancock. Latent Distribution Preserving Deep Subspace Clustering. In Proceedings of the Twenty-Eighih International Joint Conference on Artificial Intelligence. pages 4440-4446, Macao, China, August 2019. International Joint Conferences on Artificial Intelligence Organization.
[50] Mohsen Kheirandishfard, Fariba Zohrizadeh, and Farhad Kamangar. Multi-Level Representation Learning for Deep Subspace Clustering. In 2020 IEEE Winter Conference on Applications of Computer Vision ( (WAVV), pages 2028 2037, Snowmass Village, CO, USA, March 2020. IEEE.
[51] Shuai Yang, Wenqi Zhu, and Yuesheng Zhu. Residual Encoder-Decode Network For Deep Subspace Clustering. In 2020 IEEE International Conference on Image Processing (ICIP), pages 2895-2899, Abu Dhabi, United Arab Emirates, October 2020. IEEE.
[52] Changqing Zhang, Huazhu Fu, Qinghua Hu, Xiaochun Cao, Yuan Xie, Dacheng Tao, and Dong Xu. Generalized Latent Multi-View Subspace Clustering. IEEE Transactions Pattern Analysis and Machine Intelligence, 42(1):86-99) January 2020. Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
[53] Jeya Maria Jose Valanarasu and Vishal M. Patel. Overcomplete Deep Subspace Clustering Networks. In 2021 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 746-755, Waikoloa, HI. USA. Jamuary 2021. IEEE
[54] Zengyi Li, Yubei Chen, Yann LeCun, and Friedrich T Sommer. Neural Manifold Clustering and Embedding. arXiv [cs.LG], January 2022.
[55] Tianjiao Ding, Shengbang Tong, Kwan Ho Ryan Chan, Xili Dai, Yi Ma, and Benjamin D Haeffele. Unsupervised Manifold Linearizing and Clustering, pages 5450-5461, October 2023.
[56] Tianzhe Chu, Shengbang Tong, Tianjiao Ding, Xili Dai, Benjamin David Haeffele, Rene Vidal, and Yi Ma. Image clustering via the principle of rate reduction in the age of pretrained models. arXiv preprint arXiv:2306.0522 306.0222. 2023.
[57] Benjamin Haeffele, Chong You, and René Vidal. A Critique of Self-Expressive Deep Subspace Clustering. 2020.
[58] Ehsan Elhamifar and René Vidal. Sparse manifold clustering and embedding. Advances in neural information processing systems, 24, 2011.
[59] Athinodoros S. Georghiades, Peter N. Belhumeur, and David J. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE transactions on pattern analysis and machine intelligence, 23(6):643-660, 2001.
[60] Sameer A Nene, Shree K Nayar, Hiroshi Murase, et al. Columbia object image library (coil-20). 1996.
[61] Maryam Abdolali and Nicolas Gillis. Beyond Linear Subspace Clustering: Comparative Study of Nonlinear Manifold Clustering Algorithms. ISBN: 2103,10656 Publication Title: arXiv [cs. March 2021.
[62] Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. In International Conference on Machine Learning, pages 89-97. PMLR, 2013.
[63] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages PMLR, 2021.
13

---

[64] Nikolas Adaloglou, Felix Michels, Hamza Kalisch, and Markus Kollmann. Exploring the Limits of Deep Image Clustering using Pretrained Models. ISBN: 1709.17896 Publication Title: arXiv [cs.CV], March 2023.
[65] René Brandenberg, Abhi Dattasharma, Peter Gritzmann, and David Larman. Isoradial bodies. Discrete & Computaaionnll Geometry, 32:447-457, 2004.
[66] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
[67] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 4171 1161, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
[68] Ery Arias-Castro, Guangliang Chen, and Gilad Lerman. Spectral clustering based on local linear approximations. 2011.
[69] Ery Arias-Castre Gilad Lerman, and Teng Zhang. Spectral clustering based on local pea. Journal of Machine Learning Research, 18(9):1-57, 2017.
[70] Xu Wang, Konstantinos Slavakis, and Gilad Lerman. Multi-manifold modeling non-euclidean spaces. In Artificial Intelligence and Statistics, pages 1023-1032. PMLR, 2015.
[71] Xu Wang, Konstantinos Slavakis, and Gilad Lerman. Riemannian multi-manifold modeling. arXiv preprint arXiv: 1410.0095, 2014.
[72] Anna Little, Mauro Maggioni, and James M. Murphy. Path-Based Spectral Clustering: Guar- antees, Robustness to Outliers, and Fast Algorithms. Journal of Machine Learning Research, 21(6):1-66, 66, 2020.
14

---

A Proofs
A.1 Proof of Lemmal
Proof of Lemma ?
To prove Lemma 1 we start by defining the condition for the solution to (WCC)
be manifold preserving in the following lemma.
Proposition 1. Let v² be the dual direction as defined in Definition S !f
krg;"")| < w Va, M (MMM, M1,
(A.1)
then every optimal solution
WMC) is manifold preserving.
The proof of Proposition T given Section
A.2 Now, from A.I. have that
[Tgz w | (Trg IP (ps(")) +
Ps'
")'))\ S (z P3(v")) (e,, Ps (v*)
(A.2)
where (.) and P3 (-) denote the projections S and the subspace orthogonal to S, respectively. Thus, we see that the stronger condition
(",, (T) P3- (v")) < wy
(A.3)
satisfied for all vy M 11 then
A.I
satisfied.
Bounding (īj g2 (v") |- From KKT conditions, we have that V² A(T X sct)), where (c", v*)
the primal-dual optimal solution to
2.5
2.6 So.
|| 11'3-
la
|| (X(--xx'')) x)c2))11
|P (Auill2
(A.4)
Adist( (7.
where (i) follows since X Xec is the linear combination of data samples in S and so, Xze E S. Furthermore, we have
dist(7, 8) = min {1i - =1
Σ
agTit
ZLENOM;
< mln - =212:
Σ
Og
Σ
Ok = 1}
ZLENNM;
ZLENO
min
y/
[
Σ
OK [
(A.5)
ZEENOM
min
[ll 2112 :
Σ
Σ
4 1}
ZLENOM,
ZIEN
dist(y,S):
From A.4
and A.5 we have
Kr,, P' (v" )) || (v*)12 S (( Va, E EM) M,
(A.6)
Combining AA3) and A.6 we have stronger condition
{ (z
(z ) + A A| 1ldiss((y. S) < ww Vzy (M,
M1, V E M Mj,
(A.7)
and equivalently, if
A " - Kr Ps(x^)
(A.8)
dist(y. (). 1F
then A.
is also satisfied, and every optimal solution to WMC is manifold preserving. We can as
write A.8
W || Py(""M
min M,
(A.9)
dist(y, S)
15

---

Bounding [13((")) 12
The dual constraint of (2.6) can be written as
|X S w 1
| 3 (1" + Ps (v")) $1
5 )l 11
(A.10)
ps((mt)
Vaz E MMMN
wi
Recall the definition of the symmetric convex body Q3 conv { 3; 2, M1 nN] as given in
W
Definition 6 From the last inequality in (A.10), we have that Pz(v") belongs to the polar set of Q3 W
i.c., i.c.,P'(MM) (r")") E (Qg) )
Proposition 2 (165). For symmetric convex body P, the inradius of P and the circumradius of its polar set 7o satisfy
r(P))(PP)) =
(A.11)
W
Using the fact that ||Pg("")] < R(CC)), and setting P = Qs in A.11
we have that
(12( 05 W S1
(A.12)
equivalently,
1
[P (12 w
(A.13)
Thus, from A.l
A.9 and (A.13).
that if w
(Tg.
|P ( )aa
Vz, E M M,,
(A.14)
W dist(y. (y. S)
then every optimal solution to (WCC) is manifold preserving.
However, if A is too small, then the optimal solution (WMC) will be trivial, i.c., c 0. Thus. to get non-trivial optimal solution to (WMC), À cannot be too small. The following proposition provides a lower bound on get a non-trivial solution.
Proposition 3. If > w disll,) then every optimal solution to WMC is nonzero.
Proof. We prove the result by contradiction. Assume that is an optimal solution to (WMC). Then, from KKT condition applied to (WMC). we have that = A Xc)= = Ay. where v the optimal solution to the dual (2.). We have that
BBBl dist S.) and
1x Ml A||X" Wl
X|XX
(A.15)
Furthermore, we have
5y kol.
| + P (T))....--
(A.16)
=|,x3 (IP loc,, 1.
Combining (A.15) and A. A. we have
X
X| --c
(T)
(A.17)
A X
> À min
1 2
Ar
|| 313371
2,
16

---

where the last equality follows since the inradius, rW (as defined in Defintion 6). can be written as
> X| o..
W
min WEB.
max R
|uu/2
min NE3,ug00
|
Furthermore, we have
[ = - 17 2 2
(T) 17 - -is-ddissS.... S) 2 1 1 dysty, (A.18)
where the last inequality follows from (A.5). Substituting this in 4A.17.. we have
1 2 >r (1 - dist(y, S)) > 1,
(A.19)
where the last inequality follows since p - Thus, we have that when À r" distty-))s(ysss) c cannot be an optimal solution since the constraint in the dual problem 2.3
is violated. This proves the statement of the proposition.
From Proposition and A.14
that if
KE (M
1
Wyr
[P )ll
min M,M, wW dist(y, 5
(A.20)
W (1 dist(y, S))
then get interval for acceptable values of À to get non-trivial and manifold preserving solution to (WMC). Rearranging the terms in (A.20), we see that,
Wyr
M of
r dist(y. S) rW (1Tl12 dist(y.
min By M,
Le.,
TTa1l2
wyr W
100 S ( M M2
(A.21)
min M,M
||
di < 1
wyr
I ( ITy
1 min 2y 3yEM
W (g()")))
then there exists a non-empty interval A*)
min
(3(0") >>
7. ("Mll distly-dsst(.SS)) EM:M,
And for any (2',*)), every optimal solution (WMC) manifold preserving.
A.2 Proof of Proposition 1
Proof of Proposition 7 To prove Proposition [ we need to derive conditions (based on an optimal
solution the reduced (2u6 for which any optimal solution to (WMC) will be manifold preserving. We do so by (i) defining conditions on primal-dual feasible solutions to (WMC) and its dual (2.3) that ensure manifold preserving optimal solution (WMC) (see Lemma 4 and then (ii) constructing such primal-dual feasible pair to (WMC) from the optimal primal-dual solution to the reduced problem 2.5) and its dual (2.6).
The following lemma provides conditions for any optimal solution (WCC) to be manifold preserv- ing. A similar result given in [62] for linear sparse clustering problem. In this work, have adapted (62, Lemma 12] for our proposed model (WMC).
Lemma 4. Let v) be primal-dual feasible solution to MMC and its dual 2. such that has support B where B BCA AC
( (1.....N), and the dual feasūble solution satisfies:
1. (W-TX") 1BV=
sgn(
2. =
3. X
Ann= S 1.
4. |X 11
17

---

Then every optimal solution (c", v²*) to WMC and its dual 2..
satisfies
c²== = 0.
Proof. (c"",e!l) ,e(3)an) "e(,)el,,,,))rer be an optimal solution to WMC
We then have
1c'"|l,,w" + A 2 c 1.w + || 1w + 11 11.w 2 1
2
|ca I.w (sgn((W)) (We )B (Wc)a)
(A.22)
+ 1 + || 11. + 2
| 122
We now determine a lower bound on | from the following proposition. Proposition 4. For any 7 > 0, the function
1 g(e) = 6 6xx
=e"e)
(A.23)
2
has unique maximizer ex and g(t = 3112" 1 1. Setting 7 = X, we have
A
2 | 11 g(E
2 (e)
(A.24)
TT 2 =ee
X 1 + (2
Also, from condition in the lemma, we have
(WW))W)), (We)a) = ((W-T) xx==xx1 )2)))x1(( - -(Wc)))
(v, N - -CR))
(c.X(cc - -c) - (v. X An (cānn:)) (v, XvxXx
A= (c)t)).
(A.25)
Combining (A.22).
A.24 and (A.25,, we have
| ll.w + A
|e"1
|cBlla, + ||e13
2
Ic 11,, (v, X AnB (cAnne))
(A.26)
1 - (v, X x: (c()))
+ (v, X(ct - c)) + (de, -E).
Now, from condition 2 in the lemma, we have that
(v. X(c" <)) + (Ae,e" - 2) = (v, X(c
+ - z) =0
(A.27)
where the last inequality follows since (c,z) and (c" are both feasible to (WMC) and so, Xc+e Xe** e Furthermore, we have that
Icenne XM,X AnBB (nn=(Cinn=)) = |ccnee Il,, ((W-T ANBBU, ((Wc'")
2 1eAneell., |X'nB=U/lxx ICAAnelli.w
0,
(A.28)
where the last inequality follows from condition 3 in the lemma. Similarly, we have that |ccte 11.w - (v. Aa (ctt)) = |c - ((W- XX " LA ((We**) aa))))))
(A.29)
11 - 11 bloc.ww.-)))
18

---

Combining (A.26).
A.27
and A.29 and using the fact B is the support of e, we have A.28
||e 1.W +
||lla,
2
Iell
| 11, (1- 11- 1). (A.30)
From condition 4 in the lemma, we know that X loo, 1. Since (e" ," ,²*) is optimal, this implies that || 1. O, and therefore, (W c A O. proving the result.
Lemma 4 provides conditions for any optimal solution of (WMC) to manifold preserving. Now, construct feasible solution (c, v)) to (WMC) that satisfies the conditions given in Lemma 4 from an optimal solution (c", 2" ,,,""")))))""" to the reduced problem (2.5) and its dual (2.6) as follows:
Cj a for j such that Ij E MM, NN
(A.31)
otherwise,
= X Age = y Xc=e, and
(A.32)
V=
(A.33)
We observe that (c, E, v) is feasible to (WMC) by construction. Let T be the set of indices of data samples in the set M1 n, and let B be the support of c² From KKT conditions for the reduced problem (2.5) and its dual (2.6). we have
de
de,
and
(A.34)
W W-TX sgn W WC = (W- x" BV sgn((W)) Thus, (c, e, v) satisfies the first two conditions in Lemma Moreover, we have that
(A.35)
X X Aonn S <1x |X S1,
(A.36)
which shows that condition 3 from Lemma 4 is satisfied for (c, Finally, we observe that condition 4 in Lemma can be equivalently written as
(z), w Vx, E M M
(A.37)
Thus, we have that if (A.7]) is satisfied, then all conditions in Lemma 4 are satisfied, and every optimal solution [MCC) manifold preserving.
A.3 Proof of Lemma
Proof of Lemmal 2 We prove the result using geometric properties of the manifold and location of the data samples. In the proof, we will introduce several new quantities and notations.
We define the curvature of the manifold Mj at y to be k. From the definition of the curvature of the smooth manifold, we have that 1/k is the radius of the largest internal tangent sphere to the manifold Mj at y. Let the tangent circle be denoted by T and let be the center of the (D 1) -idimenniional internal tangent sphere. Consider a point of intersection of the sphere B with T and denote it by Next, we project the point on to the line connecting y and z, and denote the projected point by u.
We then have that the points 2, u and v form vertices a right-angled triangle, and we have
= u112 = || v + ||0 u112
(A.38)
We now determine the bounds on each of the quantities in (A.38).
Since is the center of the sphere T of radius 1/K, and lies on the surface of the sphere, we have
1
2 " u1
(A.39)
R²
Now consider the three points y, u and v. Since is the projection of the point on the line connecting y and z, we have that the three points and also form a right-angled triangle. Thus, we have that
| 2 < ||u =1
(A.40)
where the last inequality follows since lies on the boundary of the sphere B with radius ( and centered
19

---

Finally, we bound 2| 2/12. Since is the projection of point u on to the line connecting y and we have that 2, v and y collinear and they lie single line connecting y and We, therefore, have that || - 2112 = lyy =||2 || y/l2. Furthermore, since is the center of the tangent sphere to the manifold M at y. we have that |!y 2||2 =11-
x² Thus,
1= 1 1 vll2-
(A.41)
Proposition 5. For the point defined above, we have dist(y, S) S 11 u112.
Proof. Let BT be the set consisting of u and additional di unique points of intersection the sphere B with T. We have that dim (aff(
BTT) I d1. Since each point in the set BT lies on the boundaries of both and T, we have that each point æ E BT is equidistant from both y and 2. Thus, and every point E BT projects onto the same point (v) the line connecting y and z. Furthermore, we have that
BT)), i.., e is the projection of y onto the affine subspace aff( : x E BT).
ly u112 dist(y. aff(2
(A.42)
From the definition of the inner tangent circle T, we have that the affine subspace (a E BT) will intersect with manifold M1 at points outside the sphere B. Thus, aff(2: x E BT) is an affine subspace of dimension S dj spanned by points not in B. From the definition of S (see Definition] 3 and Assumption] 2
we note that is the affine subspace (of dimension di) nearest to y, and spanned by the points inside or the sphere B. Thus, we have that dist(y, S) S dist(y, aff(x x E BBT)).
(A.43)
Combining A.42 and A.43 proves the result.
From A.4 and Proposition we bound ||= u112 as
|| 2112 S dist(y- (y. S).
(A.44)
Combining (A.38.
A.39
A.40 and A..44). ), we have that
c² + dist(y, R²
(A.45)
or equivalently,
( dist(y, 5)
2
2
- 5²
(A.46)
R²
Since re)ch(Mi) 2 S, and from Definition 8
Me))h(MM)) we have that 2 Ç, and thus,
dist(y, V R2
-2.
(A.47)
Rearranging the terms proves the result.
B Details of Experiments Real Data
B.1 CIFAR Datasets and CLIP feature extraction
CIFAR Datasets. CIFAR consists of 50,000 training and 10,000 test color images of size 32x32. They are equally divided into 10, 20, and 100 classes resulting CIFAR-10, CIFAR-20, and CIFAR- 100 datasets respectively. The 20 classes in CIFAR-20 are obtained by merging 100 classes in CIFAR- 100 into disjoint groups
CLIP Pre- Fre-Training Model. Contrastive Language-Image Pre-training (CLIP) 63 is an efficient tool for image representation learning by jointly training an image encoder and a text encoder to correctly predict the image-text pairings. We use ViT-L/14 [66] architecture for image encoder. ViT-L/14 refers 'Large' Vision Transfomer model with input images divided into patches of size 14x14. See [67] for more information on the definition of 'Large' models. We use the features extracted from images CIFAR dataset by CLIP pre- pre-training model that uses ViT-L/14 architecture
We use the CLIP package available http:///gihaa..mmmmoeeac//c/lttp
20

---

B.2 Details of Experimental Setup
We include details of experiments performed in Section 3.2 Note that, the results reported in Table
| for SSC, EnSC, CPP and TEMI methods are taken from 56 Please refer to [36] Section 4] for experimental details.
L-WMC and E-WMC. We perform the steps in Algorithm for clustering data using L-WMC and E-WMC. Details pre-training using CLIP (Step of Algorithm|]] [ are provided in Appendix [B.] To construct the representation matrix (Step 2), we define the models L-WMC and E-WMC for each input data sample with the distance matrix W set as given Section 3.2.2 We use an efficient active-set solver given in [18] to solve the optimization problem. The experiments are performed on a machine with (R) (R) Gold 6130 CPU operating at 2.10 GHz frequency and with 37 GB code in the Supplementary material.
RAM. We have provided
We use grid search over the following parameter values: 7) E {1, 20, 100, 400) and {20, 50) x Ao. where λn is the smallest value of À that generates a non-trivial (non-zero) solution. We report the best accuracy results in Table Furthermore, @ the values of the parameters and corresponding to the clustering results reported in rows 1 (L-WMC) and 2 (E-WMC) in Table [
CIFAR-TO
CIFAR-20
CIFAR-100
Method/ Parameter values
X
7
"
L-WMC
50
20
50
400
50
20
E- E-C
20
400
20
400
50
400
Table 2: Values of the parameters corresponding to the clustering results reported Table for L-WMC and E-WMC.
SMCE. The MATLAB code for the ADMM algorithm was provided by the authors of [58]. We implemented the ADMM algorithm that solves SMCE [58] in Python. We refer to this method as SMCE this paper. As discussed in Section 3.2.2 we apply SMCE to pre-trained data generated using CLIP. To generate the representation matrix, SMCE solves the following optimization problem for each input sample 24.
minn>|/Waa W|W + 12al11 s.t. 1 1,
min
(B.1)
where W; is a diagonal matrix whose j-th entry [Wils = w/ Eege 100 1 and Q,
Note that the matrix W; is the same as the matrix W defined for our model L- جهو
WMC. Furthermore, since the l does not select points that are very far from the given data point Ii, (58) consider only K nearest neighbors of the point x, in the algorithm where K is chosen a priori. We use grid search to choose the values of the hyperparameters and K: 7 {10, 20, 50) and K (10, 20, 50, 100). providees the best clustering result achieved by SMCE for each of the three datasets. In Table 3 we provide the parameter values corresponding to the clustering results
reported for SMCE in Table
CIFAR-10
CIFAR-20
CIFAR 100
Method/ Parameter values
7
K
7
K
7
K
SMCE
10
20
50
20
20
20
Table 3: Values of the parameters corresponding to the clustering results reported in Table for SMCE.
B.3
Constructing affinity
The first step in using spectral clustering to cluster the input data samples to construct an affinity matrix that indicates pairwise similarities between the data samples. Ideally, the data samples from the same cluster should highly connected while those from different clusters should have no connections. For the models based on self-expressiveness property, the construction of the affinity
21

---

matrix involves post-prccessing the representation matrix C. Several post-pnnn post-processing strategies have been used in literature construct a symmetric affinity matrix from the representation matrix. We describe three commonly used strategies below.
Normalize (N): This strategy of constructing affinity matrix involves normalizing each column of the representation matrix C' to have unit E2 norm. This strategy can be helpful when the imput data samples have different norms.
Symmetric (S): This is one of the commonly used strategies construct the affinity matrix A as A= +==1 (CI²).
k-NN (K): This strategy involves finding & nearest neighbors of each data sample. Note that, the representation matrix can have dense connections. When k-NN strategy is applied to each column of C, only the largest entries in the column are preserved while the rest are set to O. Thus, the affinity matrix resulting from this strategy will have at most k non-zero entries in each column. This strategy can be helpful when there are several nonzero entries in C' of very small magnitude.
We use N, S. K to denote the three strategies from now Moreover, 'symmetric', 'normalize' and 'k-NN' strategies are used one after the other (and in that order) on the representation matrix C' to construct the affinity matrix. Since no universally best strategy exists, we construct an affinity matrix by defining all permutations of all possible subsets of the three strategies described above. Thus, there are 15 possible ways to construct an affinity by applying the following strategies on C: N, S, K, NK, KN, SN, NS, SK, KS, SNK, SKN, K KSN, KNS, NSK, NKS. After constructing the affinity matrix using each strategy or a combination of strategies, we use k-means to cluster the data.
SNK to denote that
For the clustering results reported in Table [ for L-WMC, E- B-WMC, and SMCE, provide the affinity construction strategy corresponding to these results in Table
Method/Dataset
CIFAR-10
CIFAR-20
CIFAR- 100
L-WMC
N
SNK
N
E-WMC
NK
SNK
N
SMCE
S
SNK NS
Table 4: Strategy used to construct affinity from the representation matrix corresponding to the clustering results reported in Table [ for L-WMC and E-WMC.
We observed that the CLIP feature vectors for each image in the CIFAR datasets have different le norm. Thus, the columns of the resulting representation matrix C' also have different sizes (E2 norm). this case, it seems intuitive normalize the columns of C' while constructing the affinity. Indeed, from Table 4 we notice that the best clustering accuracy result was observed when the affinity construction involved normalizing the representation matrix C.
C Review of Manifold Clustering Methods with Theoretical Guarantees
Distance between Tangent Spaces The work of (68) provides an algorithm that i) fits an affine subspace to local neighborhood of each point in the dataset and ii) computes the similarity between two points based on the distance between the two subspaces well as that between the two points. Further, they provide an upper bound on Euclidean distances between data samples from different clusters to achieve perfect clustering with high probability. Interestingly, the above was later extended to allow for faster computation based on prototypes (69 and the ambient space being a Riemannian manifold [70 71]. However, their theoretically guaranteed algorithms require knowledge of the intrinsic dimension of each manifold (or implicitly model selection parameter to estimate the dimension) which is in practice typically not known apriori and hard to estimate.
Longest-Leg Path Distance The work of 72 provides an algorithm that computes distance in a different way: for every two points x, y in a given set of data points, the distance between is the minimum over all paths connecting 2, y the longest leg in the path. Then, the similarity can be computed by applying a kernel function to the distances. They provide theoretical guarantees that allow for general number of manifolds, as well as algorithms that approximate the distances hierarchically.
22

---

Nonetheless, the approaches have been only tested on smaller- scale datasets (i.e., either ambient dimension, or number of data samples, or number of clusters being small, while this paper shows both theoretical guarantees
well clustering performance on large-scale datasets of natural images. direction of independent interest to the community is understand the computational picture of these methods on such datasets, which is not pursued by this paper.
23

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have provided access to our code to reproduce the results. In case of synthetic data, we have included the code reproduce the data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have included the details experimental setup. The experimental results from other works also included in the paper. In such cases, have also included references to the source.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification; For the experiments on synthetic data, we report error bars and the experimental settings for the random data.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have included the details the computational resources the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We have conformed the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work does not have a direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The models or the data used in the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: When existing models or results were used, we have cited the original work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
28

---

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


Reviews:
[{"review_id": "yZnQ8UQH8Y", "reviewer": "Reviewer_XZ5T", "summary": "The authors addresses the problem of clustering high-dimensional data that lie on multiple, low-dimensional, nonlinear manifolds. They propose a new method that clusters data belonging to a union of nonlinear manifolds, providing geometric conditions for a manifold-preserving representation. \nA significant contribution of the paper is the provision of geometric conditions that guarantee the correct clustering of data points on the same manifold. The authors validate their method through experiments on CIFAR datasets, demonstrating competitive performance compared to state-of-the-art methods, although it performs marginally worse than methods without theoretical guarantees.", "questions": "No questions.", "limitations": "Strategy of choosing $\\lambda$", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The proposed method is novel and interesting. Also, the geometric conditions are pretty clear. The conditions require that the manifold is well-sampled and sufficiently separated from other manifolds, with the sampling density given as a function of the curvature. The proofs in the paper are very clear and well written\n\nThe method is tested on the CIFAR datasets, showing competitive performance compared to state-of-the-art methods, even though it performs marginally worse than methods without theoretical guarantees.", "weaknesses": "Maybe will be useful give insights about how choose the hyperparameter $\\lambda$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your strong support in the acceptance. Your comments are to the point, and we provide a reply below hoping to alleviate your concerns. \n\n**How to choose the hyperparameter $\\lambda$ in practice:**\n\nBoth reviewers XZ5T and Mh3Q pointed out this question. Our answer has two parts:\n- Guided by Lemma 3, if one has an estimate of the norm of the data points, curvature of the manifold, and within-manifold data density (i.e. $\\zeta$), then the lower bound, $\\lambda_l$, of $\\lambda$ can be estimated. One can search $\\lambda$s that are near to or greater than $\\lambda_l$. \n- When the above quantities are difficult to know, one can alternatively rely on a heuristic grid search to find $\\lambda$ on a training set, as we do in Appendix B.2. \n    - The use of $\\lambda_0$ in line 672 of the paper follows from the work of [A] (their $\\S$ 4.2.2) and [18] (their $\\S$ 4.2 and Appendix F). The idea is that, $\\lambda_0$ rules out a family of hyperparameters that lead to the solution $c$ being all zeros; such $c$’s are useless since they suggest that every point forms its own cluster. \n    - To figure out what $\\alpha$ to use, we run experiments on CIFAR-100 data to grid search over $\\alpha = \\{2,5,10,20,50\\}$. Since $\\alpha = 20,50$ provided the best results, we used these values for the remaining experiments. \n\nWe will include this discussion under Lemma 3, and refer to it in the experiments (section 3.2.2). Thank you for helping us make the paper more self-contained!\n\nBest Regards, \n\nAuthors of Submission 17809\n\n\n\n[A] C. You, “Sparse Methods for Learning Multiple Subspaces from Large-scale, Corrupted and Imbalanced Data”, 2018.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MsgeD8JI47", "reviewer": "Reviewer_yHKx", "summary": "This paper attempts to present a theoretical analysis for a slightly modified sparse manifold clustering method, showing that under some condition on the data distribution, the separation between different manifolds and the curvature of the manifold, the optimal solution is point-wise subspace preserving and thus implies manifold preserving. In addition, the range of the hyperparameter $\\lambda$ is derived and can be nonempty (if the density of the data in the manifold is high enough). Empirical evaluations are conducted on both synthetic data (to validate the theoretical results) and CIFAR10/20/100 with pretrain CLIP feature.", "questions": "1. The formulation in Eq.(1.1) is a modification from SMCE [57]. What is the essential difference from the weighted sparse model in SMCE?\n\n2. Why such a constraint $1^\\top c =1$ is imposed on the objective as a penalty? Is there any geometric interpretation? \n\n3. Compared to the strict constraint, what is the reason to relax it as a penalty term?  Moreover, is the parameter $\\eta$ set as very large? If not, why not simply impose an affine constraint to have an affine combination? \n\n4. In Eq. (WMC), a homogenization of the data is used, rather than using the raw data. So, are the input data properly normalized or not? Why or why not? Since that $\\eta$ should be as large as possible, is that reasonable to appending a very large component on the data vector $x$? \n\n5. Since that the data points are neighboring points and the data are not normalized (the reviewer did find out the normalization step), what can we expect the size of the inradius? \n\n6. The experiments are insufficient and less convincing. \n\n- The performance comparison is neighther complete nor fair enough. Since that the so-called WMC is similar to SMCE (as discussed in L55-L66), SMCE is the most important baseline method. However, the experimental results listed in Table 1 don't include SMCE. Thus, the empirical evaluation is less convincing. \n\n- For the results of EnSC and SSC listed in Table 1, is there some suitable postprocessing adopted as that in L-WMC or E-WMC? How much the performance improvement is coming from the spetial postprocessing step? What about the performance when the baseline methods also adopt a proper postprocessing? \n\n7. In L42: the piled prior works are deep subspace clustering methods, none of them is for nonlinear manifold clustering method. Also, it is not a good practice to pile many citations in a single bracket.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper derives the theoretical  condition to guarantee the manifold preserving solution for the modified sparse manifold clustering model (which is based on a sparse self-expressive model). \n\n+ The paper provides clear geometric interpretations on the derived theoretical conditions, also the curvature of the manifold is connected to the density of the data per manifold.", "weaknesses": "1. The formulation in Eq.(1.1) is nothing but a trivial modification from SMCE [57]. \n\n- In SMCE, it also adopts a locality weighted $\\ell_1$ norm based regulizer. To be specific, the so-called L-WMC uses a linerly weighting scheme (as in L295), which is exactly the same as that in SMCE (where the weight matrix is $Q_i$).  So, what is the essential difference from the weighted sparse model in SMCE?\n\n2. An extra constraint $1^\\top c =1$ is imposed on the objective function as a penalty term. Why such a constraint $1^\\top c =1$ is imposed on the objective as a penalty? Is there any geometric interpretation? \n\n3. Compared to the strict constraint, what is the reason to relax it as a penalty term?  Moreover, is the parameter $\\eta$ set as very large? If not, why not simply impose an affine constraint to have an affine combination? \n\n4. In Eq. (WMC), a homogenization of the data is used, rather than using the raw data. So, are the input data properly normalized or not? Why or why not? Since that $\\eta$ should be as large as possible, is that reasonable to appending a very large component on the data vector $x$? \n\n5. Since that the data points are neighboring points and the data are not normalized (the reviewer did find out the normalization step), what can we expect the size of the inradius? \n\n6. The experiments are insufficient and less convincing. \n\n- The performance comparison is neighther complete nor fair enough. \nSince that the so-called WMC is similar to SMCE (as discussed in L55-L66), SMCE is the most important baseline method. However, the experimental results listed in Table 1 don't include SMCE. Thus, the empirical evaluation is less convincing. \n\n- For the results of EnSC and SSC listed in Table 1, is there some suitable postprocessing adopted as that in L-WMC or E-WMC? How much the performance improvement is coming from the spetial postprocessing step? What about the performance when the baseline methods also adopt a proper postprocessing? \n\n7. In L42: the piled prior works are deep subspace clustering methods, none of them is for nonlinear manifold clustering method. Also, it is not a good practice to pile many citations in a single bracket.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time in reviewing our paper. We are happy to address your comments below.\n\n**(W1, W2, W3, W6) Comparison with SMCE**\n\nIt was questioned how our method differs from SMCE, why such a difference is needed, and if the difference is significant. \n- We agree that our formulation (1.1) differs from SMCE by penalizing the affine constraint. \n- The modification is motivated by the goal of providing theoretical guarantees of non-linear manifold clustering methods. \n    - With the affine constraint in the SMCE model, we are unable to provide an upper bound on $\\lambda$. This prompted us, by necessity, to relax the constraint as a penalization leading to (1.1), which allows us to derive the bounds and theorems in section 2.\n- The focus and contributions of this paper are therefore two-fold:\n    - Providing geometric conditions that guarantee a manifold preserving solution of (1.1) in terms of curvature, sampling density, separation between the manifold;\n    - Showing that (1.1) performs comparably to the state-of-the-art manifold clustering algorithms.\n\n\n**(W2) Geometric interpretation of the constraint $1^Tc = 1$ or its penalty version**\n- The affine constraint in SMCE is motivated by the fact that a manifold can be locally approximated by an affine subspace. \n- Making it a soft penalty with multiplier $\\eta$ is equivalent to homogenizing the data with homogenization constant $\\sqrt{\\eta}$, i.e., (WMC) is equivalent to (1.1). \n\nWe will include the clarification in the preamble of section 2, thanks for the comment!\n\n**(W3) Is the parameter $\\eta$ set as very large?**\n\nIn our experiments, the parameter $\\eta$ is not chosen to be very large. We chose 3 different values of $\\eta$ proportional to: (a) empirical mean of $||x||^2$, (b) empirical mean of $||x||$, and (c) the value 1.\n\n**(W4) In Eq. (WMC), a homogenization of the data is used, rather than using the raw data. (Part 1) So, are the input data properly normalized or not? Why or why not? (Part 2) Since that $\\eta$ should be as large as possible, is that reasonable to appending a very large component on the data vector $x$? (Part 3)**\n- Part 1: Eq. (WMC) is equivalent to the objective (1.1), i.e., objective with affine constraint penalization, as we explained in the response above. \n- Part 2: We did not normalize the input data. As a result, we see that the quantities in our geometric result (Lemma 1) depend on the norm of the data samples. We observe that the same analysis can be used for normalized data samples, which results in a special case. \n- Part 3: Great question! \n    - Making $\\eta$ as large as possible has two effects: on the one hand, it helps enforce the affine constraint. On the other hand, it diminishes the importance of the reconstruction error term in (1.1); a different perspective is that the large $\\eta$ dominates the computation of the Euclidean norm of the homogenized points. \n    - So it is not reasonable to append a large $\\eta$ to the data sample $x$. Thus, rather than choosing an arbitrarily large value for $\\eta$ in our experiments, we choose $\\eta$ as described in the response of W3.\n\n**(W5) Since that the data points are neighboring points and the data are not normalized (the reviewer did find out the normalization step), what can we expect the size of the inradius?**\n\nThe size of the inradius does depend on the size of the data samples. If the norm of few (or all) data samples scales up, then the inradius will also scale up. However, note that this relationship is not linear. Furthermore, we believe that simply scaling up or down all the data samples by a constant will not have a significant impact on the theoretical results (Lemma 1) since other quantities (apart from inradius) involved in the result also change accordingly.\n\n**(W6) The experiments are insufficient and less convincing.**\n\n**1. The performance comparison is neighther complete nor fair enough. Since that the so-called WMC is similar to SMCE (as discussed in L55-L66), SMCE is the most important baseline method. However, the experimental results listed in Table 1 don't include SMCE. Thus, the empirical evaluation is less convincing.**\n\nThe goal of our experiments was to compare the performance of WMC with current state-of-the-art methods and show that WMC performs only slightly worse than these methods while also providing a theoretical understanding of the model.\n\n**2. For the results of EnSC and SSC listed in Table 1, is there some suitable postprocessing adopted as that in L-WMC or E-WMC? How much the performance improvement is coming from the spetial postprocessing step? What about the performance when the baseline methods also adopt a proper postprocessing?**\n\nEnSC and SSC did adopt/use post-processing; in particular, they use the symmetric normalization strategy (“S” in Appendix B.4). We also used the post-processing strategy described in Appendix B.4 when SSC method was used to cluser points in CIFAR-10 dataset. The clustering accuracy was observed to 86.4% (compared to 96.07% for our method).\n\n**(W7) In L42: the piled prior works are deep subspace clustering methods, none of them is for nonlinear manifold clustering method. Also, it is not a good practice to pile many citations in a single bracket.**\n\nWe thank the reviewer for the suggestion, which we will certainly adopt for the final submission.\n\n\nBest Regards, \n\nAuthors of Submission 17809", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3BpD7dXSsW", "reviewer": "Reviewer_Mh3Q", "summary": "The authors present a novel approach for nonlinear manifold clustering that comes with both a solid theoretical background and provable guarantees as well as some experiments indicating practical applicability.", "questions": "What is the reason for choosing the values in the grid search for the hyperparameters in the way you did?", "limitations": "The authors discuss some limitations in Section 4 of the manuscript.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and in this reviewers opinion fits very well into Neurips. The studied problem is relevant for many applications. The proofs that this reviewer has checked appear to be correct.", "weaknesses": "The main downside I see is that the proposed method relies on many crucial hyperparameters, and the authors could go into a bit more detail into how these parameters should be selected in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your positive evaluation of our work, especially for acknowledging that *“the paper … in this reviewers opinion fits very well into Neurips”*. Thank you for the constructive comments, which we address below.\n\n**How to choose hyperparameters:**\n\nThere are three hyperparameters of the method, $W$, $\\eta$, and $\\lambda$, which we discuss below.\n- Choosing $W$: We define the weight matrix such that each entry $(i,j)$ is proportional to (a) the distance between data samples $x_i$ and $x_j$ (see model L-WMC), (b) the exponential of the distance between $x_i$ and $x_j$ (see model E-WMC).\n- Choosing $\\eta$: We perform a grid search over multiple lambda values, and the following grid values for eta: (a) 1 (b) empirical mean of $||x||2$, (c) empirical mean of $||x||_2^2$. \n- Choosing $\\lambda$: Please kindly refer to the response to Reviewer XZ5T.\n\nWe hope this alleviates your concern; if not, we are happy to engage with you during the discussion session. Thank you for the question!\n\nBest Regards, \n\nAuthors of Submission 17809", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thanks to all the reviewers for their time and input on the paper. We appreciate that reviewers found the paper *novel and well-written* (XZ5T, Mh3Q), believe we provided *clear geometric conditions* (yHKx, XZ5T), *illustrated competitive performance* (XZ5T), and that our work is *relevant for many applications* (Mh3Q). 

We address individual concerns below. Please feel free to communicate with us during the discussion phase if you have further concerns.

Thank you and regards, 

Authors of Submission 17809

Meta-review: The paper studies the problem of manifold clustering, in which we are given data on multiple (nonlinear) manifolds and would like to segment data based on their membership. The paper studies an approach to this problem inspired by subspace clustering, in which each data point is approximated by a sparse (approximately) affine combination of the other samples, and then spectral clustering is applied to the resulting coefficients. The paper’s main results are theoretical: it studies conditions under which solutions to this optimization problem are manifold-preserving, i.e., i.e., nonzero coefficients all correspond to samples from the correct manifold. The paper provides two different phrasings of these results: one in terms of convex bodies spanned by certain subsets of samples, and one in terms of manifold curvature. Experiments show that this method is applicable to learning datasets such as CIFAR-X, with better performance than subspace clustering methods (albeit a bit below state-of-the-art for these datasets). 

Reviewers generally praised the theoretical novelty of the paper: although subspace clustering has been extensively analyzed, there is far less existing work on manifold clustering. Concerns focused on the choice of hyperparameter lambda, the role of the affine constraint in the formulation and the experiments. After considering author feedback, reviewers uniformly recommend acceptance: the paper provides a novel theoretical characterization of a natural computational approach to this important class of nonlinear models. 

The AC concurs and recommends acceptance, with one caveat, as follows: 

As a technical note, claims such as Lemma 2 (and hence Lemma 3) require not only assumptions on the *curvature* of the manifold, but on its *reach* [originally defined in a 1959 paper of Federer, and widely used in the theoretical analysis of algorithms for nonlinear data, e.g., manifold estimation / approximation]. Lemma 2 quantifies the error in a local, affine approximation to M_1. The claimed property only holds if the points from M_1 in the neighborhood B have small intrinsic distance to y. In general, M_1 can exit this neighborhood, ``loop around’’ and re-enter it, in which case the claimed bound can fail. If zeta(B) is smaller than the reach, this does not happen, points in the *extrinsic* neighborhood B are *intriniscally local*, in which case the conclusion of the lemma is correct. [A standard assumption would be that zeta(B) < reach(M_1); this is related to the paper’s stated assumption, since we always reach(M_1) <= 1/curvature(M_1), but ensures that the extrinsic neighborhood B is intrinsically local]

This issue should be carefully addressed in the final version.
Decision: Accept (poster)