Geometric Analysis of Nonlinear Manifold Clustering

Authors: nimita  shinde
tianjiao  ding
daniel p robinson
rené  vidal
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:06:38

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

Main paper: 
 introduction: 
 Manifold clustering is a fundamental problem in data science, in which one seeks to cluster data lying close to a union of low-dimensional manifolds. It has a vast number of applications, such as clustering i) image pixels [1] [2] [3] , ii) video frames [4, 5] , iii) images of faces [6] , hand-written digits [7] or other natural objects [8] , iv) rigid-body motions [9] , v) human actions [10] [11] [12] , and vi) searching policies for robots [13] , to name a few.Over the past two decades, there has been a considerable amount of work on subspace clustering, the special case where each manifold is a 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.e., given a data point y and matrix of data points X, it holds that y = Xc for some vector c. The observation that the support of the sparsest such c should correspond to data points in the same subspace as y prompted the study of the optimization problem where r(•) is a regularizer on c (e.g., ∥ • ∥ 1 to promote sparsity [6] ) and λ > 0 is a parameter that balances the two terms in the objective. By solving an instance of (SC) for each point in the dataset, one obtains one coefficient vector c per point, and the matrix of all coefficients for all points can be used to build a similarity graph of the points and run spectral clustering to obtain a clustering of the data. This has spurred a fruitful line of research, leading to various formulations based on different regularizers [6, [14] [15] [16] [17] [18] [19] [20] , efficient algorithms [18, 21, 22] , and theoretical guarantees on c having the correct support [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] .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 [34] cannot be well modeled by low-dimensional subspaces. Instead, it is more natural to assume that each cluster is modeled by a smooth low-dimensional nonlinear manifold, a 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 is absent.Although a few nonlinear manifold clustering methods have achieved high clustering accuracy on large-scale datasets, they lack a theoretical justification. For example, the work in [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] 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 [54] [55] [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 a local neighborhood of a manifold approximately as a lowdimensional affine subspace, and solves a modified version of (SC) that reweights data and adds an affine constraint 1 T c = 1. Despite its effectiveness on simpler datasets such as 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.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-expressiveness of the input sample y:EQUATIONwhere W is a diagonal matrix with j-th diagonal entry w j an increasing function of the Euclidean distance between y and data sample x j . The regularizer ∥W c∥ 1 was adopted from SMCE to promote sparse solutions with support determined by "close" data points. Comparing (1.1) with (SC), we see two differences: (i) (1.1) replaces r(c) with a new regularizer that is a function of c and W , and (ii) (1.1) penalizes violation of the constraint 1 T c = 1 in the objective by introducing the term (1 -1 T c) 2 . Thus, as η goes to infinity, the data sample will be represented by an affine combination of input data samples. It is then natural to ask the following question: Question 1. Can we provide geometric conditions based on the input data samples and structure of the underlying manifolds that ensure that every optimal solution to (1.1) is manifold preserving, i.e., the non-zero entries of an optimal solution c correspond to data from the same manifold as y?In this paper, we propose a model that generates an approximately affine representation of an input data sample and provide an answer to Question 1. Our contributions are summarized below.• Formulation: We propose to perform manifold clustering via the convex optimization problem (1.1), which is based on a self-expressiveness property. Notably, the proposed formulation can be efficiently solved using a fast active-set-based method. We then construct an affinity matrix based on the solutions to (1.1), and then use spectral clustering to cluster the data. • Theory: Using our new formulation, we provide an answer to Question 1 by giving theoretical guarantees for any optimal solution of (1.1) to be manifold preserving (see Definition 1). 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.• Experiments: We compare the performance of the proposed method with state-of-the-art alternatives on CIFAR-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.For l = 1, . . . , L, we let M l denote a nonlinear manifold in R D with intrinsic dimension d l ≪ D.We define M = ∪ L l=1 M l to be the union of manifolds. Let N data samples be generated from M, which we represent as the columns of X = [x 1 , . . . , x N ] ∈ R D×N . Additionally, let y be a new sample generated from the union of manifolds M. Without loss of generality, we assume that y ∈ M 1 . Furthermore, for l = 1, . . . , L, let M l denote the set of generated input data samples that lie on M l , and define M = ∪ L l=1 M l to be the set of all N data samples. For a given subspace S, we let P S (x) denote the orthogonal projection of x onto the subspace S.Outline. In Section 2, 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 on real data. We conclude the paper in Section 4. 
proposed model and theoretical analysis: 
 The model (1.1) we study is obtained by penalizing the affine constraint 1 T c = 1 in SMCE [58] with penalty parameter η. The penalty term in the model (1.1) is equivalent to homogenizing the data samples with homogenization constant √ η. Thus, we we propose to study the equivalent problemmin c ∥W c∥ 1 + λ 2 ∥e∥ 2 2 s.t. e = y -Xc (WMC)where λ > 0, W is a diagonal matrix with positive entries that depend on the Euclidean distances between y and the input data samples, X ∈ R (D+1)×N is the matrix whose j-th column, x j , is the homogenized data sample (x T j , √ η) T with η > 0 a chosen constant, and y := (y T √ η) T . One could define w j := W jj = ∥x j -y∥ 2 /( k ∥x k -y∥ 2 ), although other reasonable choices are possible.In this section, we state our assumptions and define key quantities used in the theoretical results. Our theoretical analysis provides an answer to Question 1, i.e., we provide conditions under which the non-zero entries of a solution c * of (WMC) correspond to data samples from the same manifold as y.If c satisfies this property, it is called a manifold preserving solution, as we now define.Definition 1 (Manifold preserving). For the data sample y ∈ M 1 , we say that the optimal solution c * to (WMC) is manifold preserving if and only if c * j = 0 for all x j / ∈ M 1 .If one considers solving N instances of problem (WMC) (each instance is defined by replacing y with x j , and removing x j from X), then the N solutions may be used to define a similarity graph. If the solution to each instance is manifold preserving, then the similarity graph will only have intra-cluster connections (no inter-cluster/false connections). Consequently, it would be expected that applying spectral clustering to such a 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 c * to (WMC) is manifold preserving.Assumption 1. We assume that each manifold is smooth and the input data samples generated on each manifold are noiseless. Furthermore, we assume that at least d l + 2 samples are generated on each manifold M l , where we recall that d l is the intrinsic dimension of manifold M l .Definition 2 (Set of nearest neighbors N). For the data sample y ∈ M 1 , define B to be the Ddimensional ball of smallest radius centered at y such that it contains d 1 + 1 points from M 1 , where d 1 is the dimension of manifold M 1 . Define N to be the set of all data samples in B excluding y, and note that N may contain samples from both M 1 and ∪ L l=2 M l .Definition 3 (Nearest affine subspace S). For the data sample y ∈ M 1 and N in Definition 2, we define the nearest affine subspace, S, as the affine subspace generated by the set N ∩ M 1 , i.e., S := aff({x j :x j ∈ N ∩ M 1 }). (2.1)Furthermore, we define S := span{x j : x j ∈ N ∩ M 1 } as the linear subspace spanned by the homogenized data samples from the set N ∩ M 1 .Assumption 2. For the affine subspace S defined in Definition 3, we assume that dim(S) = d 1 .Equivalently, we assume that dim(S) = d 1 + 1.Figure 1 : The affine space S approximates the tangent to the 1-dimensional manifold M 1 at y.{x i } 4 j=1 ⊂ N and that {x 1 , x 2 } ⊂ M 1 .The affine subspace S is spanned by the d 1 + 1 points nearest to y on the manifold M 1 (see Figure 1 for an illustration when M 1 is one-dimensional). We can view S as an approximation of the tangent space to M 1 at y.We now define the dual of (WMC) since our analysis requires knowledge of the dual variables.Definition 4 (Weighted ℓ 1 norm and its dual). The dual norm of the weightedℓ 1 norm ∥c∥ 1,W := ∥W c∥ 1 is ∥c∥ ∞,W -1 := max ∥z∥ 1,W ≤1 c T z = max j∈[N ] |c j | w j . (2.2)We can write the dual of (WMC) asmax ν∈R D+1 ⟨y, ν⟩ -1 2λ ∥ν∥ 2 2 s.t. ∥X T ν∥ ∞,W -1 ≤ 1.(2.3) The constraint in (2.3) can be equivalently written as |⟨x j , ν⟩| ≤ w j for all 1 ≤ j ≤ N.(2.4)We now define two more quantities (Definitions 5 and ( 6)) that appear in our main results (see Lemma 1 and Lemma 3). Remark 1 also gives additional insight to these quantities.Definition 5 (Dual direction). For the data sample y ∈ M 1 , define X S as the matrix with columns that span the linear subspace S in Definition 3, i.e., X S = [x j ] xj ∈N∩M1 . Define the reduced problemEQUATIONand its corresponding dualmax ν ⟨y, ν⟩ -1 2λ ∥ν∥ 2 2 s.t. ∥X T S ν∥ ∞,W -1 ≤ 1. (2.6)Then, we define the dual direction ν * as the unique optimal solution to (2.6).The dual direction ν * is used to define the separation between the manifold M and other manifolds. We elaborate on this in Remark 1.Definition 6 (Inradius r(Q W S )). For the data sample y ∈ M 1 , defineQ W S = conv ± x j w j : x j ∈ N ∩ M 1 . (2.7)We define r(Q It follows from Definition 6 that the inradius r W increases as {w j } decrease. Since {w j } are proportional to the distances between y and the d 1 + 1 points closest to y in the set M 1 , the inradius increases when more samples are generated from M 1 near y (see Remark 1 for more details).Our first theoretical result provides geometric conditions that ensure that an optimal solution of (WMC), defined for a given input data sample y, is manifold preserving (see Definition 1). Lemma 1. For y ∈ M 1 , input data X, and λ > 0, define the model (WMC) and let Assumptions 1 and 2 hold. Let S and S be defined as in Definition 3, and ν * and r W be as given in Definitions 5 and 6, respectively. Let dist(y, S) be the Euclidean distance between y and subspace S, and defineγ W = min x k ∈M\M1 w k r W - |⟨x k ,P S (ν * )⟩| ∥P S (ν * )∥2 ∥x k ∥ 2 .The following statements hold.(a) If γ W > 0 and (2.8)dist(y, S) < ∥y∥ 2 γ W 1 + γ W ,(2.9)then the interval (λ l , λ u ) := 1 r W (∥y∥2-dist(y,S)) , γ Wr W dist(y,S) is well defined and nonempty.(b) If λ ∈ (λ l , λ u ), then every optimal solution to (WMC) 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 1. For the d 1 -dimensional manifold M 1 , conditions (2.8) and (2.9) depend on the following:1. Inradius r W : r W (see Definition 6) provides information of the distribution of the d 1 + 1 closest data samples to y on the manifold M 1 , i.e., the samples belonging to the set M 1 ∩ N. The inequalities in (2.8) and (2.9) are more easily satisfied if r W increases. From the definition of the inradius r W , it is clear that r W increases when the samples in the set M 1 ∩ N are more uniformly distributed. Furthermore, suppose we generate more samples from the manifold M 1 near y. Then, the distances of the d 1 + 1 samples in the set M 1 ∩ N from y will decrease, resulting in a larger inradius. Thus, r W increases when either the number of samples generated from the manifold M 1 near y increases or the samples in the set M 1 ∩ N are well-distributed.2. Inner product |⟨x k , P S (ν * )⟩|: For each x k ∈ M \ M 1 , the inner product defines the separation between x k and the subspace S. If the separation between each point x k ∈ M \ M 1 and S increases, the inner product decreases. From the definition of γ W , it is clear that the inequalities in (2.8) and (2.9) are more easily satisfied when the separation increases.Part (a) of Lemma 1 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 (λ l , λ u ) to be nonempty. Note that λ l is a function of y and X while λ u is a function y, X, and λ since γ W depends on ν * , which is an optimal solution to (2.6) with parameter λ.Part (b) of Lemma 1 states that if the hyperparameter λ satisfies λ l < λ < λ u , then every solution to (WMC) is manifold preserving and nonzero. While we can choose λ > λ l based on knowledge of (y, X), to explicitly compute λ satisfying λ < λ u (when such a value exists) requires defining λ u as a function of λ. Although Lemma 1 does not provide this relationship, numerical experiments in Section 3.1 on randomly generated data clarify how λ l and λ u change as a function of (y, X) and λ.Interestingly, a geometric result in [62] for a linear subspace model can be recovered from Lemma 1.Corollary 1 (Special case of (WMC)). For y ∈ M 1 , input data X, and λ > 0, define the model (WMC) with W = I. Assume that ∥y∥ 2 = ∥x j ∥ 2 = 1 for each data sample x j , and that Assumptions 1 and (2) hold. In addition to the quantities defined in Lemma 1, defineµ = max x k ∈M\M1 |⟨x k , P S (ν * )⟩| ∥P S (ν * )∥ 2 ,and let r = r W ≡ r I since W = I. It then follows from Lemma 1 that if µ < r and dist(y, S) < r-µ 1+r-µ , (2.10)then the interval 1 r(1-dist(y,S)) , r-µ rdist(y,S)) is well defined and nonempty. Moreover, if λ is in this interval, then every optimal solution to (WMC) is manifold preserving and nonzero. Furthermore, if the manifolds are linear, then dist(y, S) = 0 since y ∈ S. Thus, in this special case, if µ < r, then for any λ > 1/r, every optimal solution to (WMC) is subspace preserving and nonzero.Although we believe the results in the previous section are 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 M 1 as well as the reach of the manifold M 1 . Let us define the curvature and the reach of a manifold. Definition 7 (Curvature of a manifold). Let M 1 be a smooth manifold with y ∈ M 1 . If 1/κ is the radius of the largest (internal) tangent circle to M 1 at y, then the curvature of M 1 at y is κ. Definition 8 (Reach of a manifold). Let M 1 be a smooth manifold. The reach of the manifold M 1 , reach(M 1 ), is the largest value such that for any x / ∈ M 1 and dist(x, M 1 ) ≤ reach(M 1 ), x has a unique projection onto M 1 . If κ is the curvature of the manifold M 1 , then reach(M 1 ) ≤ 1/κ.In Figure 1 , κ denotes the curvature of the 1-dimensional manifold M 1 at y. The curvature of the manifold at y gives a bound on how fast the direction of a point on 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 M 1 at y, the radius of the ball B centered at y, and dist(y, S). Then, in Lemma 3, we provide geometric conditions based on the curvature that guarantee that any optimal solution of (WMC) is manifold preserving. Lemma 2. Let Assumptions 1 and 2. For y ∈ M 1 , let B and S be as defined in Definitions 2 and 3, respectively. Let ζ = ζ(B) be the radius of the sphere B, κ be the curvature of the manifold M 1 at y, reach(M 1 ) be the reach of the manifold M 1 , and dist(y, S) be the Euclidean distance between y and the subspace S.If reach(M 1 ) ≥ ζ, then dist(y, S) ≤ 1 κ - 1 κ 2 -ζ 2 .(2.11)Combining Lemma 1 and Lemma 2 gives our final result. Lemma 3. For y ∈ M 1 , input data X, and λ > 0, define the model (WMC) and let Assumptions 1 and 2 hold. In addition to the quantities defined in Lemma 1, let ζ be the radius of the sphere B, κ be the curvature of the manifold M 1 at y, and reach(M 1 ) be the reach of the manifold M 1 . The following then hold.(a) Ifγ W > 0, (2.12) reach(M 1 ) ≥ ζ, and(2.13)EQUATIONthen there exists a non-empty interval (λ l , λ u ) :=1 r W ∥y∥2-1 κ + 1 κ 2 -ζ 2 , γ W r W 1 κ - 1 κ 2 -ζ 2 . (b) If λ ∈ (λ l , λ u ), then every optimal solution to (WMC) is manifold preserving and nonzero.The quantity γ W in Lemma 3 captures the notion of distribution of the data samples in the set M 1 ∩N as well as separation of the data samples not in M 1 from S. The condition (2.12) requires γ W to be positive. Condition (2.13) is related to the sampling density of the manifold M 1 near y. If the number of samples generated on M 1 near y increases, then ζ will decrease. Meanwhile, if the curvature κ of the manifold at y is large, 1/κ will be small, and from Definition 8, we see that reach(M 1 ) will be small. This indicates that for (2.13) to hold, one may need to generate more samples on M 1 near y. Finally, (2.14) provides a lower bound on γ W based on κ (the curvature) and ζ (the number of samples generated on M 1 near y). When all three of these conditions hold, we have a non-empty interval (λ l , λ u ) as defined in Lemma 3(a). If λ l < λ < λ u , then Lemma 3(b) ensures that every optimal solution to (WMC) is manifold preserving and nonzero.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 no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
computational results: 
 In this section, we first perform experiments on randomly generated data to understand how the quantities in Lemma 1 change as a function of the input data and the hyperparameter λ (see Subsection 3.1). 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, it performs only slightly worse in terms of clustering accuracy.In this section, we perform two experiments designed to understand how λ l and λ u (see Lemma 1) change as a 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 R 100 . The embedding of data involves generating a random orthonormal basis of a subspace in R 100 , followed by projecting the samples generated from two trefoil knots onto this subspace. We choose η = 1 and define the matrix W as a diagonal matrix with j-th diagonal entry w j = ∥y -x j ∥ 2 / k ∥y -x k ∥ 2 .Experiment 1: {λ l , λ u } versus λ. For this experiment, we evaluate how the values of λ l and λ u change when only λ changes. We generate N 1 ∈ {120, 150, 160, 200} and N 2 = 40 data samples from two non-intersecting trefoil knots of intrinsic dimension d 1 = d 2 = 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 of λ l and λ u for different values of λ ∈ [4.8, 204.8] × 10 -4 in Figure 2 .Since λ l is independent of λ, its value is constant for all values of (N 1 , N 2 ). It also appears that λ u is a monotonically increasing function of λ that eventually reaches a "steady-state" value. When N 1 = 120, we observe that the conditions in Lemma 1(a) are not satisfied for any value of λ, and that the interval (λ l , λ u ) is empty. When N 2 = 150, we observe that λ u > λ l for λ > 0.0012, but for these λ values it also holds that λ > λ u , meaning that Lemma 1(b) is violated for all λ > 0.When N 1 ∈ {160, 200}, we observe that for some values of λ > 0, there exist non-empty intervals (λ l , λ u ) such that λ ∈ (λ l , λ u ). Thus, for every such λ ∈ (λ l , λ u ), it follows from Lemma 1 that every optimal solution to (WMC) is manifold preserving and nonzero. We can conclude from these experiments that for certain input data (y, X), there exists a range of acceptable values of λ for which the conditions defined in both parts (a) and (b) of Lemma 1 are satisfied, so that every optimal solution to (WMC) is nonzero and manifold preserving.0.001 0.002 0.010 0.005 0.000N 1 =120, N 2 =40 l u 0.001 0.002 0.010 0.005 0.000 N 1 =150, N 2 =400.001 0.002 0.010 0.005 0.000N 1 =160, N 2 =400.001 0.002 0.010 0.005 0.000 0.005 Experiment 2: {λ l , λ u } versus N . In this experiment, we aim to understand how λ l and λ u change when the number of data samples, N , changes. We let N 1 = N 2 and gradually increase N = N 1 + N 2 . We generate 50 different random embeddings of data samples from trefoil knots in R 100 . For each pair of data (y, X), we compute λ l and then create three values for λ by setting λ = αλ l for α ∈ {2, 5, 50}. Then, for each λ value, we plot λ l and λ u versus N = N 1 + N 2 in Figure 3 . We can observe that as the number of samples increases, the size of the interval (λ l , λ u ) increases linearly.N 1 =200, N 2 =40We further observe that for α = 2, the interval (λ l , λ u ) is non-empty (satisfying the conditions in Lemma 1(a)) for all N ≥ 890, whereas for α = 5, 50, the interval is non-empty for all N ≥ 300. Thus, we see that the small value of α leads to a slower increase in λ u resulting in the interval (λ l , λ u ) becoming non-empty at a much larger value of N . Furthermore, we also see that, (i) when α = 5, λ ∈ (λ l , λ u ) for all N ≥ 330, and (ii) when α = 50, λ ∈ (λ l , λ u ) for all N ≥ 510. In other words, when α = 5, the conditions in both parts (a) and (b) of Lemma 1 are satisfied for all N ≥ 330, whereas when α = 50, the conditions in parts (a) and (b) of Lemma 1 are satisfied for all N ≥ 510, making λ = 5λ l , the best choice of the hyperparameter in this experiment. In this section, we compare the empirical performance of our model with existing methods on CIFAR-10, CIFAR-20, CIFAR-100 datasets [33] . The CIFAR dataset consists of 60000 color images of size 32×32 that are divided into 10, 20, and 100 classes for CIFAR-10, CIFAR-20, CIFAR-100, 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.1 for more details.)We follow the steps in Algorithm 1 to cluster the input images using our model (WMC).Algorithm 1 Pseudocode for clustering data using (WMC) Input: Images from CIFAR dataset, λ > 0, and the number of clusters L 1: Generate features using the CLIP encoder [63] . The CLIP (Contrastive Language-Image Pre-Training) [63] 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 1 of Algorithm 1. Step 2 of Algorithm 1 employs our model WMC to construct a representation matrix C. We now briefly explain this step. For the feature vector y of each input image: (a) we define the positive diagonal distance matrix W so that each diagonal entry is an increasing function of the Euclidean distance between y and each of the other feature vectors, (b) we define the model (WMC) for λ > 0, (c) we solve (WMC) using an active-set method [18] to (hopefully) obtain a manifold preserving representation for the feature vector of each input image. (The choice of λ and W is explained further in Subsection 3.2.2.) Similar to classical spectral clustering methods, the representation matrix is used to define a symmetric affinity matrix A; here, we choose A = Table 1 : Comparing clustering accuracy (ACC) and Normalized Mutual Information (NMI) for our models L-WMC and E-WMC with state-of-the-art subspace clustering and deep clustering methods. Each method is used to 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 in blue. [56, 64] for details on fine-tuning models. Output metrics. 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.In this section, we compare the numerical performance of two instances of our Algorithm 1 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 CLIP features extracted from the input images. The two instances of our Algorithm 1 are determined by how the weight matrix W is chosen in (WMC), as we now describe.• L-WMC: Linearly Weighted Manifold Clustering model with w j = ∥x j -y∥ 2 / k ∥x k -y∥ 2 for all j in (WMC). Here, the weights {w j } are linearly proportional to the Euclidean distances.• E-WMC: Exponentially Weighted Manifold Clustering model with weights in (WMC) defined asw j = exp(2∥x j -y∥ 2 )/ k exp(2∥x k -y∥ 2 ) for all j.Here, the weights {w j } are defined as an exponential function of the Euclidean distances.We report the clustering results for L-WMC and E-WMC in Table 1 . (See Appendix B.2 for details on the choice of λ and η.) From Table 1 , we can observe that the clustering accuracy of L-WMC and E-WMC is consistently better than EnSC, SSC and SMCE for all three datasets. Moreover, L-WMC and E-WMC perform slightly worse than the state-of-the-art method CPP on the CIFAR-10 and CIFAR-20 datasets. So, although our method does not outperform the existing state-of-the-art method, our method is the first to perform similarly to the state-of-the-art methods and have a theoretical guarantee of correctness (see Lemma 1 and Lemma 3).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: We have provided access to our code to reproduce the results. In case of synthetic data, we have included the code to reproduce the data.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion: 
 In this paper, we propose a model whose solution defines a self-expressive representation of the input data, and provide a theoretical analysis of correctness of the model (see Lemma 1 and Lemma 3). For data (y, X) and hyperparameter λ > 0, we give conditions under which the solution to our 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-art methods on CIFAR datasets.For a given data set, our analysis does not provide a strategy for choosing the hyperparameter λ > 0 so that it satisfies the conditions in Lemma 1. This leads to an important open question: For any given data set, can one provide a proof of existence of λ > 0 for which the conditions in Lemma 1 are satisfied? If so, can one provide a closed form expression to choose the value of λ? An answer to this question will result in an "optimal" choice for the value of λ, thus avoiding the cost of tuning λ.A.1 Proof of Lemma 1Proof of Lemma 1. To prove Lemma 1, we start by defining the condition for the solution to (WMC) to be manifold preserving in the following lemma.Proposition 1. Let ν * be the dual direction as defined in Definition 5. If|⟨x j , ν * ⟩| < w j ∀x j ∈ M \ M 1 , (A.1)then every optimal solution to (WMC) is manifold preserving.The proof of Proposition 1 is given in Section A.2. Now, from (A.1), we have that|⟨x j , ν * ⟩| = |⟨x j , P S (ν * ) + P S ⊥ (ν * )⟩| ≤ |⟨x j , P S (ν * )⟩| + |⟨x j , P S ⊥ (ν * )⟩|, (A.2)where P S (•) and P S ⊥ (•) denote the projections on to S and the subspace orthogonal to S, respectively. Thus, we see that if the stronger condition|⟨x j , P S (ν * )⟩| + |⟨x j , P S ⊥ (ν * )⟩| < w j (A.3)is satisfied for all x j ∈ M \ M 1 , then (A.1) is satisfied.Bounding |⟨x j , P S ⊥ (ν * )⟩|. From KKT conditions, we have that ν * = λ(y -X S c * ), where (c * , ν * ) is the primal-dual optimal solution to (2.5)-(2.6). So,EQUATIONwhere (i) follows since X S c * is the linear combination of data samples in S and so, X S c * ∈ S. Furthermore, we have dist(y, S) = min a {∥y -z∥ 2 : z =x k ∈N∩M1 a k x k } ≤ min a {∥y -z∥ 2 : z = x k ∈N∩M1 a k x k , x k ∈N∩M1 a k = 1} = min a y √ η - z √ η 2 : z √ η = x k ∈N∩M1 a k x k √ η = min a {∥y -z∥ 2 : z = x k ∈N∩M1 a k x k , x k ∈N∩M1 a k = 1}= dist(y, S).(A.5)From (A.4) and (A.5), we have|⟨x j , P S ⊥ (ν * )⟩| ≤ ∥x j ∥ 2 ∥P S ⊥ (ν * )∥ 2 ≤ λ∥x j ∥ 2 dist(y, S) ∀ x j ∈ M \ M 1 . (A.6)Combining (A.3) and (A.6), we have a stronger condition|⟨x j , P S (ν * )⟩| + λ∥x j ∥ 2 dist(y, S) < w j ∀ x j ∈ M \ M 1 , (A.7)and equivalently, ifλ < w j -|⟨x j , P S (ν * )⟩| dist(y, S)∥x j ∥ 2 ∀ x j ∈ M \ M 1 , (A.8)then (A.1) is also satisfied, and every optimal solution to (WMC) is manifold preserving. We can write (A.8) asλ < min xj ∈M\M1 w j - |⟨xj ,P S (ν * )⟩| ∥P S (ν * )∥ dist(y, S)∥x j ∥ 2 . (A.9)Bounding ∥P S (ν * )∥ 2 . The dual constraint of (2.6) can be written as ∥X T S ν * ∥ ∞,W -1 ≤ 1 ⇒ ∥X T S (P S (ν * ) + P S ⊥ (ν * ))∥ ∞,W -1 ≤ 1 ⇒ ∥X T S P S (ν * )∥ ∞,W -1 ≤ 1 ⇒ x k w k , P S (ν * ) ≤ 1 ∀x k ∈ M 1 ∩ N.∥P S (ν * )∥ 2 r(Q W S ) ≤ 1, (A.12)or equivalently,∥P S (ν * )∥ 2 ≤ 1 r W . (A.13)Thus, from A.1, (A.9) and (A.13), we see that ifEQUATIONthen every optimal solution to (WMC) is manifold preserving.However, if λ is too small, then the optimal solution to (WMC) will be trivial, i.e., c = 0. Thus, to get a non-trivial optimal solution to (WMC), λ cannot be too small. The following proposition provides a lower bound on λ to get a non-trivial solution.Proposition 3. If λ > 1 r W (∥y∥2-dist(y,S)) , then every optimal solution to (WMC) is nonzero.Proof. We prove the result by contradiction. Assume that λ > 1 r W (∥y∥2-dist(y,S)) , and c = 0 is an optimal solution to (WMC). Then, from KKT condition applied to (WMC), we have that ν = λ(y -Xc) = λy, where ν is the optimal solution to the dual (2.3). We have that∥X T ν∥ ∞,W -1 = λ∥X T y∥ ∞,W -1 ≥ λ∥X T S y∥ ∞,W -1 . (A.15)Furthermore, we have∥X T S y∥ ∞,W -1 = ∥X T S (P S (y) + P S ⊥ (y))∥ ∞,W -1 = ∥X T S (P S (y))∥ ∞,W -1 . (A.16)Combining (A.15) and (A.16), we have∥X T ν∥ ∞,W -1 ≥ λ∥X T S P S (y)∥ ∞,W -1 = λ∥X T S P S (y)∥ ∞,W -1 ∥P S (y)∥ 2 ∥P S (y)∥ 2 ≥ λ min u∈S,u̸ =0 λ∥X T S u∥ ∞,W -1 ∥u∥ 2 ∥P S (y)∥ 2 = (i) λr W ∥P S (y)∥ 2 , (A.17)where the last equality follows since the inradius, r W (as defined in Defintion 6), can be written asr W = min u∈S,u̸ =0 max xj ∈M1∩N λ|⟨x j /w j , u⟩| ∥u∥ 2 = min u∈S,u̸ =0 λ∥X T S u∥ ∞,W -1 ∥u∥ 2 .Furthermore, we have∥P S (y)∥ 2 = ∥y-P S ⊥ (y)∥ 2 ≥ ∥y∥ 2 -∥P S ⊥ (y)∥ 2 = ∥y∥ 2 -dist(y, S) ≥ ∥y∥ 2 -dist(y, S), (A.18)where the last inequality follows from (A.5). Substituting this in (A.17), we have∥X T S ν∥ ∞,W -1 ≥ λr W (∥y∥ 2 -dist(y, S)) > 1, (A.19)where the last inequality follows since λ > 1 r W (∥y∥2-dist(y,S)) . Thus, we have that when λ > 1 r W (∥y∥2-dist(y,S)) , c = 0 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 3 and (A. 14) , we see that if1 r W (∥y∥ 2 -dist(y, S)) < min xj ∈M\M1 w j r W - |⟨xj ,P S (ν * )⟩| ∥P S (ν * )∥2 r W dist(y, S)∥x j ∥ 2 , (A.20)then we get an interval for acceptable values of λ to get a non-trivial and manifold preserving solution to (WMC). Rearranging the terms in (A.20), we see that, if .r W dist(y, S) r W (∥y∥ 2 -dist(y, S)) < min xj ∈M\M1 w j r W - |⟨xj ,P S (ν * )⟩| ∥P S (ν * )∥2 ∥x j ∥ 2 , i.And for any λ ∈ (λ l , λ u ), every optimal solution to (WMC) is manifold preserving.Proof of Proposition 1. To prove Proposition 1, we need to derive conditions (based on an optimal solution to the reduced dual 2.6) for which any optimal solution to (WMC) will be manifold preserving. We do so by (i) defining conditions on a primal-dual feasible solutions to (WMC) and its dual (2.3) that ensure manifold preserving optimal solution to (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 of (WMC) to be manifold preserving. A similar result was given in [62] for linear sparse clustering problem. In this work, we have adapted [62, Lemma 12] for our proposed model (WMC).Lemma 4. Let (c, e, ν) be a primal-dual feasible solution to (WMC) and its dual (2.3) such that c has support B where B ⊆ A ⊆ {1, . . . , N }, and the dual feasible solution satisfies:1. (W -T X T ) B ν = sgn((W c) B ), 2. ν = λe, 3. ∥X T A∩B c ν∥ ∞,W -1 ≤ 1, 4. ∥X T A c ν∥ ∞,W -1 < 1.Then every optimal solution (c * * , e * * , ν * * ) to (WMC) and its dual (2.3) satisfies c * * A c = 0.Proof. (c * * , e (1) * * , e (2) * * ) be an optimal solution to (WMC). We then have∥c * * ∥ 1,W + λ 2 ∥e * * ∥ 2 2 = ∥c * * B ∥ 1,W + ∥c * * A∩B c ∥ 1,W + ∥c * * A c ∥ 1,W + λ 2 ∥e * * ∥ 2 2 ≥ ∥c B ∥ 1,W + ⟨sgn((W c) B ), (W c * * ) B -(W c) B ⟩ + ∥c * * A∩B c ∥ 1,W + ∥c * * A c ∥ 1,W + λ 2 ∥e * * ∥ 2 2 . (A.22)We now determine a lower bound on ∥e * * ∥ 2 2 from the following proposition. Also, from condition 1 in the lemma, we have⟨sgn((W c) B ), (W c * * ) B -(W c) B ⟩ = ⟨(W -T X T ) B ν, (W c * * ) B -(W c) B ⟩ = ⟨ν, X B (c * * B -c B )⟩ = ⟨ν, X(c * * -c)⟩ -⟨ν, X A∩B c (c * * A∩B c )⟩ -⟨ν, X A c (c * * A c )⟩. (A.25)Combining (A.22), (A.24), and (A.25), we have where the last inequality follows since (c, e) and (c * * , e * * ) are both feasible to (WMC), and so, y = Xc + e = Xc * * + e * * . Furthermore, we have that∥c * * ∥ 1,W + λ 2 ∥e * * ∥ 2 2 = ∥c B ∥ 1,W + λ 2 ∥e∥ 2 2 + ∥c * * A∩B c ∥ 1,W -⟨ν, X A∩B c (c * * A∩B c )⟩ + ∥c * * A c ∥ 1,W -⟨ν, X A c (c * * A c )⟩ + ⟨ν, X(c * * -c)⟩ + ⟨λe,∥c * * A∩B c ∥ 1,W -⟨ν, X A∩B c (c * * A∩B c )⟩ = ∥c * * A∩B c ∥ 1,W -⟨(W -T X T ) A∩B c ν, ((W c * * ) A∩B c )⟩ ≥ ∥c * * A∩B c ∥ 1,W -∥X T A∩B c ν∥ ∞,W -1 ∥c * * A∩B c ∥ 1,W ≥ 0, (A.28)where the last inequality follows from condition 3 in the lemma. Similarly, we have that∥c * * A c ∥ 1,W -⟨ν, X A c (c * * A c )⟩ = ∥c * * A c ∥ 1,W -⟨(W -T X T ) A c ν, ((W c * * ) A c )⟩ ≥ ∥c * * A c ∥ 1,W (1 -∥X T A c ν∥ ∞,W -1 ). (A.29)Finally, we bound ∥z -v∥ 2 . Since v is the projection of point u on to the line connecting y and z, we have that z, v and y collinear and they lie on a single line connecting y and z. We, therefore, have that ∥z -v∥ 2 = ∥y -z∥ 2 -∥v -y∥ 2 . Furthermore, since z is the center of the tangent sphere to the manifold M 1 at y, we have that ∥y -z∥ 2 = 1 κ . Thus,∥z -v∥ 2 = 1 κ -∥v -y∥ 2 . (A.41)Proposition 5. For the point v as defined above, we have dist(y, S) ≤ ∥y -v∥ 2 .Proof. Let BT be the set consisting of u and additional d 1 unique points of intersection of the sphere B with T . We have that dim(aff{x : x ∈ BT }) ≤ d 1 . Since each point in the set BT lies on the boundaries of both B and T , we have that each point x ∈ BT is equidistant from both y and z. Thus, u and every point x ∈ BT projects onto the same point (v) on the line connecting y and z. Furthermore, we have that ∥y -v∥ 2 = dist(y, aff{x : x ∈ BT }), (A.42) i.e., v is the projection of y onto the affine subspace aff{x : x ∈ BT }.From the definition of the inner tangent circle T , we have that the affine subspace aff{x : x ∈ BT } will intersect with manifold M 1 at points outside the sphere B. Thus, aff{x : x ∈ BT } is an affine subspace of dimension ≤ d 1 spanned by points not in B. From the definition of S (see Definition 3) and Assumption 2, we note that S is the affine subspace (of dimension d 1 ) nearest to y, and spanned by the points inside or on the sphere B. [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 to '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 in CIFAR dataset by CLIP pre-training model that uses ViT-L/14 architecture * .We include details of experiments performed in Section 3.2. Note that, the results reported in Table 1 for SSC, EnSC, CPP and TEMI methods are taken from [56] . Please refer to [56, Section 4] for experimental details.L-WMC and E-WMC. We perform the steps in Algorithm 1 for clustering data using L-WMC and E-WMC. Details of pre-training using CLIP (Step 1 of Algorithm 1) are provided in Appendix B.1.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 in 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 Intel(R) Xeon(R) Gold 6130 CPU operating at 2.10 GHz frequency and with 37 GB RAM. We have provided our code in the Supplementary material.We use grid search over the following parameter values: η ∈ {1, 20, 100, 400} and λ ∈ {20, 50}×λ 0 , where λ 0 is the smallest value of λ that generates a non-trivial (non-zero) solution. We report the best accuracy results in Table 1 . Furthermore, Table 2 provides the values of the parameters λ and η corresponding to the clustering results reported in rows 1 (L-WMC) and 2 (E-WMC) in Table 1 . 1 for L-WMC and E-WMC.MethodThe 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 in 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 x i ,min ci γ∥W i c i ∥ 1 + 1 2 ∥Q i c i ∥ 2 2 s.t. 1 T c i = 1, (B.1)where W i is a diagonal matrix whose j-th entry[W i ] jj = w j = ∥xj -xi∥2 k̸ =i ∥x k -xi∥2, andQ i = xj -xi ∥xj -xi∥2 j̸ =i. Note that the matrix W i is the same as the matrix W defined for our model L-WMC. Furthermore, since the ℓ 1 does not select points that are very far from the given data point x i , [58] consider only K nearest neighbors of the point x i in the algorithm where K is chosen a priori. We use grid search to choose the values of the hyperparameters γ and K: γ ∈ {10, 20, 50} and K ∈ {10, 20, 50, 100}. Table 1 provides the best clustering result achieved by SMCE for each of the three datasets. In Table 3 The first step in using spectral clustering to cluster the input data samples is to construct an affinity matrix that indicates pairwise similarities between the data samples. Ideally, the data samples from the same cluster should be highly connected while those from different clusters should have no connections. For the models based on self-expressiveness property, the construction of the affinity matrix involves post-processing the representation matrix C. Several post-processing strategies have been used in literature to construct a symmetric affinity matrix from the representation matrix. We describe three commonly used strategies below.• Normalize (N): This strategy of constructing affinity matrix A involves normalizing each column of the representation matrix C to have unit ℓ 2 norm. This strategy can be helpful when the input data samples have different norms. • Symmetric (S): This is one of the commonly used strategies to construct the affinity matrix A as A = 1 2 (|C| + |C| T ). • k-NN (K): This strategy involves finding k 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 k largest entries in the column are preserved while the rest are set to 0. 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 on. Moreover, we use SN K to denote that '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, N K, KN , SN , N S, SK, KS, SN K, SKN , KSN , KN S, N SK, N KS. After constructing the affinity matrix using each strategy or a combination of strategies, we use k-means to cluster the data.For the clustering results reported in Table 1 for L-WMC, E-WMC, and SMCE, we provide the affinity construction strategy corresponding to these results in Table 4 . 4 : Strategy used to construct affinity from the representation matrix corresponding to the clustering results reported in Table 1 for L-WMC and E-WMC.We observed that the CLIP feature vectors for each image in the CIFAR datasets have different ℓ 2 norm. Thus, the columns of the resulting representation matrix C also have different sizes (ℓ 2 norm). In this case, it seems intuitive to 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.Distance between Tangent Spaces The work of [68] provides an algorithm that i) fits an affine subspace to a local neighborhood of each point in the dataset and ii) computes the similarity between two points based on the distance between the two subspaces as 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 a 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 a 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 x, y is the minimum over all paths connecting x, y of 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 a general number of manifolds, as well as algorithms that approximate the distances hierarchically.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 as well as clustering performance on large-scale datasets of natural images. A direction of independent interest to the community is to understand the computational picture of these methods on such datasets, which is not pursued by this paper. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: We have included the details of experimental setup. The experimental results from other works are also included in the paper. In such cases, we 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 to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: 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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.* We use the CLIP package available at https://github.com/openai/CLIP?tab=readme-ov-file 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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. 
A 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.
strength_weakness: strength_weakness: Maybe will be useful give insights about how choose the hyperparameter $\lambda$.
questions: questions: No questions.
limitations: limitations: Strategy of choosing $\lambda$
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The formulation in Eq.(1.1) is nothing but a trivial modification from SMCE [57]. 

- 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?

2. 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? 

3. 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? 

4. 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$? 

5. 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? 

6. The experiments are insufficient and less convincing. 

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

- 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? 

7. 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.
questions: 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?

2. Why such a constraint $1^\top c =1$ is imposed on the objective as a penalty? Is there any geometric interpretation? 

3. 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? 

4. 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$? 

5. 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? 

6. The experiments are insufficient and less convincing. 

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

- 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? 

7. 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: What is the reason for choosing the values in the grid search for the hyperparameters in the way you did?
limitations: limitations: The authors discuss some limitations in Section 4 of the manuscript.

Comments: title: Responses to Authors' Responses
Responses to rebuttal
comment: Thanks for the authors' quick responses and the revision promises in the final version.

1. Normalization or not for the data is an critical issue that worth to discuss a bit in the final version. 

2. Regarding to $\eta$ and the affine constraint
- Since that the $\eta$ could not be very large, does that mean the affine constraint not helps at the end the day? Could the relaxed affine constraint be drop? If it does not work, it is nothing but a decoration or strawman. Yes, the relaxed constraint is used in the analysis.  

- On the other hand, the geometric condition to yield correct nonzero coefficients in the case of linear subspaces is very clear since Sol.&Candes(2012); but the geomtric condition of the correctness guarantee for the case of affine subspaces is rare and less intuitive.  The geometric analysis developed in the submission is built on an interesting concept called nearest affine subspace and a linear subspace of the homogenous embedding. Is there any (intrinsic) connection between the linear subspace of the homogenous embedding and the affine subspace? Is the assumption 2 probably correct (or in what case)? Is there any prior work on subspace clustering in affine setting? Or any theoretical results on the connection from affine geometry (or what else)? A few words on this point would be helpful. 

- In addition, it is called an era of large pre-trained model nowadays. But it is also an era calling for transparent "white-box" models. Is there *any* white-box model devoted for nonlinear manifold clustering? It seems that none of the method piled in L42 is.  

3. That sounds quite great if the performance SMCE could be fairly compared to the modified models. As an alternative, it is also okay to compare them on COIL100, which is a standard testbed for manifold clustering algorithms. No need to use pre-trained CILP, no need to use scatter transform or other fancy feature extraction. Use the pixels of the gray scale image as input. Then a fair comparison could be easier.  Lastly, for EnSC, rather than directly citing from prior work, reproducing it on CLIP feature (with parameters are better tuned if possible) would be more convincing. 

The responses and the promises could resolve my major concerns. Since that the developed theoretical analysis with the insightful interpretation is clear and solid enough, the reviewer would like to see an acceptance.
Thanks for your response!
We greatly appreciate your increased rating and your additional input. Below we take the opportunity to further alleviate your concerns.

*"Since the parameter $\eta$ cannot set to large, it is less reasonable to set it to infinity”*
- You are right, we will remove the claim in the revised paper. Thank you for the catch!

*“The high clustering accuracy seems owning to the pre-trained feature via CLIP”*
- All of the methods in Table 1 use CLIP: EnSC, SSC directly cluster on CLIP features; TEMI, CPP used deep networks to learn to refine and cluster CLIP features. 
- Promised Revision:  We are motivated by your comment, and in the revision, we will highlight the above in the caption of Table 1, rather than simply saying “when applied to CLIP features”. Thank you!

*“...not the slightly modification from SMCE.”*
- The modification from SMCE to our formulation WMC is for providing theoretical guarantees of manifold clustering methods, which we tried to be frank about in the rebuttal above (in comparison with SMCE). We provided the current set of experiments to further understand if the very formulation we analyze (WMC) has any impact on real large-scale applications. 
- Promised Revision: That being said, your comment is well received: Since WMC is a variant of SMCE, it is interesting to see how SMCE [57] would perform on CIFAR. To our knowledge, the largest dataset that SMCE has been tested on is MNIST as reported by the work of [60]. 
    - A main barrier that limits us from getting the results during the rebuttal period is the implementation of SMCE: the code provided by the authors of SMCE is in Matlab, and it computes an N x N (i.e., 60,000 x 60,000) dense matrix for computing nearest neighbors, which is expensive. This is even worse if we try to find the optimal parameters. 
    - We have been working on implementing SMCE in Python (for a fair comparison with the alternatives) with a modern nearest-neighbor computation. We will gladly include the result in the revised paper. 


Hopefully this alleviates your concerns. We appreciate your feedback and insights. Please let us know if you have any further concerns or suggestions.


Thanks and regards, 

Authors of Submission 17809
Thanks for the point-to-point respondes in the rebuttal. 

Since the parameter $\eta$ cannot set to large, it is less reasonable to set it to infinity (in the dicussion at the end of Section 1). 

The reviewer did not satisfy the responses for the insufficiency in experiments. The high clustering accuracy seems owning to the pre-trained feature via CLIP, not the slightly modification from SMCE. 
The reviewer appreciates the established theoretical anaysis for understanding a modified sparse manifold clustering algorithm, but not the empirical evaluation is weak. 
Had well tuned the parameters and conducted fair experiments, whanever EnSC or SMCE, could yield the similar high performance. A solid and convincing empirical evaluation could helps further.
I would like to thank the authors for their clarifying rebuttal.