Exploring a Principled Framework for Deep Subspace Clustering
Authors: Xianghan Meng
Zhiyuan Huang
Wei He
Xianbiao Qi
Rong Xiao
Chun-Guang Li
Venue: ICLR 2025 Poster (2025)
Keywords: deep subspace clustering
self-expressive model
representation learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We propose a principled framework for deep subspace clustering with theoretical justifications to avoid collapse and to promote the learned representations lying in a union of orthogonal subspaces.

Abstract: Subspace clustering is a classical unsupervised learning task, built on a basic assumption that high-dimensional data can be approximated by a union of subspaces (UoS). Nevertheless, the real-world data are often deviating from the UoS assumption. To address this challenge, state-of-the-art deep subspace clustering algorithms attempt to jointly learn UoS representations and self-expressive coefficients. However, the general framework of the existing algorithms suffers from feature collapse and lacks a theoretical guarantee to learn desired UoS representation. In this paper, we present a Principled fRamewOrk for Deep Subspace Clustering (PRO-DSC), which is designed to learn structured representations and self-expressive coefficients in a unified manner. Specifically, in PRO-DSC, we incorporate an effective regularization on the learned representations into the self-expressive model, prove that the regularized self-expressive model is able to prevent feature space collapse, and demonstrate that the learned optimal representations under certain condition lie on a union of orthogonal subspaces. Moreover, we provide a scalable and efficient approach to implement our PRO-DSC and conduct extensive experiments to verify our theoretical findings and demonstrate the superior performance of our proposed deep subspace clustering approach.

Published as a conference paper at ICLR 2025
EXPLORING A PRINCIPLED FRAMEWORK FOR DEEP SUBSPACE CLUSTERING
Xianghan Meng", Zhiyuan Huang' & Wei He Beijing University of Posts and Telccommunications, Beijing 100876, P.R. China (mengxianghan, suangzhiyual wei he @bbpp. edu.
Xianbiao Qi & Rong Xiao Intellifusion, Shenzhen, P.R. China
Chun-Guang Li
Beijing University of Posts and Telecommunications, Beijing 100876, P.R. China Lichunguanggbupt. edu.cn
ABSTRACT
Subspace clustering a classical unsupervised learning task, built on a basic assumption that high-dimensional data can be approximated by union of sub- spaces (UoS). Nevertheless, the real-world data are often deviating from the UoS assumption. To address this challenge, state-of-the-art deep subspace clustering algorithms attempt to jointly learn UoS representations and self-expressive coef- ficients. However, the general framework of the existing algorithms suffers from a catastrophic feature collapse and lacks theoretical guarantee to learn desired UoS representation. this paper, we present a Principled fRamewOrk for Deep Subspace Clustering (PRO-DSC), which is designed to learn structured represen- tations and self-expressive coefficients in a unified manner. Specifically, PRO- DSC, we incorporate an effective regularization on the learned representations into the eelf-expressive model, prove that the regularized self-expressive model able prevent feature space collapse, and demonstrate that the learned optimal repre- sentations under certain condition lie on a union of orthogonal subspaces. More- over, we provide scalable and efficient approach to implement conduct extensive experiments to verify our theoretical findings and demonstrate the superior performance of our proposed deep subspace clustering approach.
PRO-DSC and
INTRODUCTION
Subspace clustering is an unsupervised learning task, aiming to partition high dimensional data that are approximately lying on a union of subspaces (UoS), and finds wide-ranging applications, such as motion segmentation (Costeira & Kanade 1998, Vidal et al. 2008 Rao al., 2010), hybrid system
identification [Vidal 2004 Bako & Vidal 2008 image representation and clustering (Hong et al.)
2006 Lu et al. 2012) genes expression clustering (MeWilliams & Montana 2014) and
Existing subspace clustering algorithms can be roughly divided into four categories: iterative meth- algebraic geometry based methods (Vidal)
ods (Tengg 2000 Ho al., 2003 Zhang al.
2009).
et al.; 2005 Tsakiris & Vidal| (017). statistical methods (Fischler Bolles 1981), and spectral
clustering- based methods (Chen & Lerman 2009
Elhamifar & Vidal 2009 Liu et al. 2010 Lu
et al. 2012 You et al. 22066a] 22016a]/aann Zhang et al. 2021
Among them, spectral clustering based methods gain the most popularity due to the broad theoretical guarantee and superior performance.
The vital component spectral clustering based methods so-called self-expressive model
EL
hamifar & Vidal 2009 2013). Formally, given a dataset X' (01,-.. [NN where Φ, g
"Corresponding author. These authors are equally contributed.

---

Published as a conference paper at ICLR 2025
self-expressive model expresses each data point By by linear combination of other points, i.e.,
where Gyj is the corresponding self-expressive coefficient. The most intriguing merit of the self- expressive model is that the solution of the self-expressive model under proper regularizer coefficients Cjj is guaranteed to satisfy a subspace-preserving property, namely, G2 o 0 only if 2; and x; are in the same subspace (Elhamifar & Vidal 2013 Soltanolkotabi & Candes 2012 Li
the
et al. 2018). Having had the optimal self-expressive coefficients {ct J. the data affinity can be induced by |cyl + lejal for which spectral clustering is applied to yield the partition of the data.
Despite the broad theoretical guarantee, the vanilla self-expressive model still faces great challenges when applied the complex real-world data that may not well align with the UoS assumption. Earlier works devote to address this deficiency by learning a linear transform of the data (Patel) et al. 2013 2015) or introducing nonlinear kernel mapping (Patel & Vidal (014) under which the representations of the data are supposed to be aligned with the UoS assumption. However, there is lack of principled mechanism to guide the learning of the linear transforms or the design of the nonlinear kernels to guarantee the representations of the data to form UoS structure.
To handle complex real-world data, in the past few years, there is surge of interests in designing deep subspace clustering frameworks, e.g., (Ji et al. 2017: Peng et al. 2018 Zhou et al., 2018
Zhang et al. 2019a] Dang et al., 2020; Peng et al.] 2020]] Lv al. 2021 Wang et al. [223b)] Zhao
et al., (024)). In these works, usually deep neural network- representation learning module is integrated to the self-expressive model, to learn the representations
E RdxN and the self-
expressive coefficients C {cij [ in joint optimization framework. However, analyzed (Haeffele al.] 202T) that, the optimal representations Z of these methods tend to catastrophically collapse into subspaces with dimensions much lower than the ambient space, which is detrimental to subspace clustering and there is no evidence that the learned representations form a UoS structure.
In this paper, we attempt propose Principled IRamewOrk for Deep Subspace Clustering (PRO- DSC), which is able to simultaneously learn structured representations and self-expressive coeffi- cients. Specifically, in PRO-DSC, incorporate effective regularization on the learned rep- resentations into the self-expressive model and prove that our PRO-DSC can effectively prevent feature collapse. Moreover, we demonstrate that PRO-DSC under certain condition can yield structured representations forming UoS structure and provide scalable and efficient approach to implement PRO-DSC. We conduct extensive experiments on the synthetic data and six benchmark datasets to verify our theoretical findings and the superior performance of our proposed approach.
Contributions. The contributions of the paper are highlighted as follows.
1. We propose a Principled fRamewOrk for Deep Subspace Clustering (PRO-DSC) that learns both structured representations and self-expressive coefficients simultaneously, in which an effective regularization on the learned representations is incorporated to prevent feature space collapse.
2. We provide a rigorous analysis for the optimal solution of our PRO-DSC, derive sufficient condition that guarantees the learned representations to escape from feature collapse, and further demonstrate that our PRO-DSC under certain condition can yield structured representations of UoS structure.
3. We conduct extensive experiments to verify our theoretical findings and to demonstrate the supe- rior performance of the proposed approach.
To the best of our knowledge, this is the first principled framework for deep subspace clustering that is guaranteed to prevent feature collapse problem and is shown to yield the UoS representations.
2 DEEP SUBSPACE CLUSTERING: A PRINCIPLED FRAMEWORK, JUSTIFICATION, AND IMPLEMENTATION
In this section, review the popular framework for deep subspace clustering, called Self- Expressive Deep Subspace Clustering (SEDSC) at first, then present our principled framework for deep subspace clustering and provide rigorous characterization of the optimal solution and the
2

---

Published as a conference paper at ICLR 2025
property of the learned structured representations. Finally describe scalable implementation based on differential programming for the proposed framework. Please refer to Appendix A for the detailed proof' of our theoretical results.
2.1 PREREQUISITE
To apply subspace clustering to complex real-world data that may not well align with the UoS assumption, there has been surge of interests in exploiting deep neural networks to learn represen- tations and then apply self-expressive model to the learned representations, e.g., (Peng et al. 2016
2018 et al. 2017 Zhou et al. 2018 Zhang al., 2019a Dang et al. 2020 Peng et al. 2020
al. 2021 Wang ct al. 2023b; Zhao et al. 2024).
Formally, the optimization problem of these SEDSC models can be formulated as follows
min Z.C
Z ZC + + s.t. 1
where Z E RdxN denotes the learned representation, C E RNN denotes the self-expressive
coefficient matrix, and 3 > 0 is hyper-parameter. The following lemma characterizes the property of the optimal solution Z for problem
Lemma Haeffele et al. 2021). The rows of the optimal solution Z for problem are the eigen- vectors that associate with the smallest eigenvalues of (I CI - C)
In other words, the optimal representation Z in SEDSC is restricted to an extremely "narrow" sub- space whose dimension is much smaller than d, leading to an undesirable collapsed solution.
2.2 OUR PRINCIPLED FRAMEWORK FOR DEEP SUBSPACE CLUSTERING
In this paper, we attempt to propose a principled framework for deep subspace clustering that prov- ably learns structured representations with maximal intrinsic dimensions.
To be specific, we try optimize the exffexxreessive model ( while preserving the intrinsic di- mension of the representation space. Other than using the rank, which is a common measure of the dimension, inspired by (Fazel et al. [0033] Ma et al. 2007, Yu al.] 20200] Liu et al., (022), we propose to prevent the feature space collapse by incorporating the log det(-)-based concave smooth surrogate which is defined as follows:
R () == log det(I - aZ Z),
(3)
where 0 is the hyper-parameter. Unlike the commonly used nuclear norm, which is convex surrogate of the rank, the log det (-)-basedd function is concave and differentiable, offers a tighter approximation and encourages learning subspaces with maximal intrinsic dimensions 3
By incorporating the maximization of R Z;a) a) as regularizer into the formulation of SEDSC in we have a Prineipled IRamewOrk for Deep Subspace Clustering (PRO-DSC):
min 2.C
1
2 - +. B log det (I + a 2) + 2
rCC) s.t. 2 = N, (4)
2
where 7 > is hyper-parameter. Now, we will give our theoretical findings for problem (4).
Theorem (Eigenspace Alignment). Denote the optimal solution of PRO-DSC in H (Z., C.), G. Z. Z. and M, (I -I- CI)
Then G. and M. share eigenspaces, i.e., G. and M, can be diagonalized simultaneously by U E O(N) where O(N) is an orthogonal group.
Note that Theorem D provides perspective from eigenspace alignment for analyzing the property of the optimal solution. Figure aa) and (b) show empirical evidences to demonstrate that alignment occurs during the training period, where G, = Z, Zo, M, = (I Cb) (C)) Z, E Rddxs, C. 1 X and n& is batch size, are computed in mini-batch training at different epoch.
omit the constraint diag(C) 0 throughout the analysis. "The dimension equals to the multiplicity of the smallest eigenvalues of (T C) C)
Without loss of generality,
Please refer to Ma 2007) for packing-hall interpretation.
3

---

Published as a conference paper at ICLR 2025
4300
101
413
Sected aigervalio (deaceniog))
Sorted ripeonatio Inder (socreding)
Sected sigenrauu (amcendingi
(a) GG,MM M.Golle (b) (u,, Gau;/
(c) ((G))
(d) X(M)
Figure I: Empirical Validation to Eigenspace Alignment and Noncollapse Representation in Mini-batch CIFAR-100. (a): Alignment error curve during the training period. (b): Eigenspace G.a,
correlation curves measured via (uj, Gouulla for 1, nb. (c) and (d): Eigenvalue curves.
CIFAR-1 16
300
CIFAR-10P
CIFAR-10
CIFAR-109
90
444-
0.0
0.01
012
0.12
0.12
6.12
73
(a) ACC (%)
(b) SRE (%)
Figure 2: Empirical Validation to Noncollapse Representation on CIFAR-10 and C-00 Clustering accuracy (ACC%) and subspace-preserviin representation error (SRE%) are displayed under varying and 7. When collapse occurs, both ACC and SRE dramatically degenerate. The perceivable phase transition phenomenon consistent with the condition avoid collapse.
Next, we will analyze problem (4p from the perspective of alternating optimization. When Z fixed, the optimization problem with respect to (w.r.t)) C' reduces to standard self-cxpressive model, which has been extensively studied in (Soltanolkotabi & Candes) 2012; Pimentel-Alarcon & Nowak 2016 Wang & Xu 2016 Li al., 2018) Tsakiris & Vidal] 2018) On the other hand, when C' fixed, the optimization problem w.r.t. Z becomes:
min log det (I oZ Z) 21 ZC s.t. | N,
(5)
which is a non-convex optimization problem, whose optimal solution remains under-explored.
In light of the fact that G and M converge to share eigenspaces, we decompose G and M respectively. Recall that G
(N) JUT and Diag(A z Z. M CI- I с)T, by using the eigenvalue decomposition, we reformulate problem into conver problem w.r.t. {> Jim1 Minnf, (See Appendix A and have the following result.
Diag (2
Theorem 2 (Noncollapse Representation). Suppose that G and M are aligned in the same 2 Then we have: a) rank Z.) min(d, N), and b) for all i 1, -,...,,in min(d, NJ, where Z. and v. are the optimal primal solution and dual solution, respectively.
eigenspaces and 7 Ammu(()) a++min [
4x the singular values oz. 7 +v.
Theorem 2 characterizes the optimal solution for problem 5). Recall that SEDSC in (2) yields collapsed solution, where rank( Z2) < min(d, .N whereas the rank of the minimizers for PRO- DSC in (5) satisfies that rank Z.) min(d, NJ. Figure and (d), we show the curves of the cigenvalues of G2 and M,, which are computed in the mini-batch training at different epoch, demonstrating that the learned representation does no longer collapse. In Figure 2 we show the subspace clustering accuracy (ACC) and subspace-represennaaii erro (SRE) function of the parameters and 7. The phase transition phenomenon around
o²
well
(M)) a+min illustrates the sufficient condition Theorem avoid representation collapse.
For each column ej in C. SRE is computed by the ground-truth affinity.
100 x
E, (1-1 Σ, wi |egl)//le/ll. where way E (0. is

---

Published as a conference paper at ICLR 2025
2000
300
(a) X X
(b) Z Z
(c) X(3 via PCA
(d) ((3) via PCA
Figure 3: Empirical Validation to Structured Representation on CIFAR-10. Gram matrices for CLIP features X and learned representations Z are shown in (a) and (b); whereas Data visualization of the samples from three categories X (3) and Z(3) via PCA are shown in (c) and (d), respectively.
Furthermore, from the perspective of joint optimizing Z and C, the following theorem demonstrates that PRO-DSC promotes expressive matrix C under certain condition.
ootooooooooaalsueeieoooooo representation and block-diagonal self-
Theorem 3. Suppose that the sufficient conditions to prevent feature collapse satisfied. With- out loss of generality, we further assume that the columns in matrix Z are arranged into k blocks according certain N N permutation matrix T, i.e., Z [Z Zz..... Zu}. Then the con- dition for that PRO-DSC promotes the optimal solution (Z., C.) to have desired structure (i.e. T Z. and C, are both block-diagone diagonal)),,,,, is that -I-C)(I -))I- G Diag (G11, Gr,, Gas) and G3 is the block Gram matrix corresponding Zj.
G*) + 0, where
Remark 1. Theorem suggests that PRO-DSC is able promote learning representations and self-expressive matrix with desired structures, i.e., the represen- tations form a union of orthogonal sub- spaces and accordingly the self-expressive matrix is block diagona,, when the condi- tion ((I CI C)
[0
-100
condition
0.6
C)T G G") O met. We call this condition compati- bly structured coherence (CSC), which re- lates to the properties of the distribution of the representations in Z and the self-
-000
Average
0.4
5500
coefficients in C. While it is not possi- ble for give theoretical justification when the CSC condition will be satisfied in general, we do have the empirical ev- idence that our implementation for PRO- DSC with careful designs does approxi- mately satisfy such a condition and thus yields representations and self-expressive matrix with desired structure (See Fig- ure
CV)
Ct) Cs
Cq:
50
100
200
250
Iterations
Figure 4: Empirical validation to Theorem 3 in Mini-batch CIFAR-10. The mean curves of the absolute values of the in-block-diagonal diagonal entries (thick) and the off-block-diageee block-diagooal entries (thin) are displayed along with the CSC condition (gray) during training PRO-DSC.
In Figure show the curves for the compatibly structured coherence (CSC) condition, and for IC, IC,CC, computed in mini-batch during training PRO-DSC CIFAR-10. As illustrated, the CSC condition is progressively satisfied and consequently the average off-block values |G, G and |C, C gradually decrease, while the average in-block values |G and C gradually increase, which empirically validates that PRO- DSC promotes block-diagonal G2 and C.
the average values of the entries in GG G G 1.
Please refer Appendix B.2 for more details about Figures

---

Published as a conference paper at ICLR 2025
2.3 SCALABLE IMPLEMENTATION
Existing SEDSC models typically use autoencoders to learn the representations and learn the self- expressive matrix C through an N x N fully-connected layer (Peng al. 2016; 2018) Ji et al. 2017 Zhou et al. 2018: Zhang et al. (0199)). While such implementation is straightforward, there are two major drawbacks: a) since that the number of self-expressive coefficients quadratic the number of data points, solving these coefficients suffers from expensive computation burden; b) the learning process is transductive, i.c., the network parameters cannot be generalized to unseen data.
To address these issues, similar to (Zhang et al. 2021). we reparameterize the self-expressive co- efficients Cij by a neural network. Specifically, the input data æ; fed into neural network h(: M): TR + Rd yield normalized representations, i.e.,
y; = =a /)/| V)
(6)
where denotes all the parameters in h-)). Then, the parameterized self-expressive matrix C generated by:
C = P(YT))
where Y y W1...... yNd dx and P(-) is the sinkhorn projection Cuturi 2013 3). which has
been widely applied in deep clustering (Caron et al. 2020; Ding et al. 2023) To enable efficient representation learning, we introduce another learnable mapping f(: +
R. for which
2j faz; 0 0)/1l((;; 0)1l2
the learned representation for the input zy, where denotes the parameters in f(-) to learn the structured representation Ze [21...., øN| R
Therefore, our principled framework for deep subspace clustering (PRO-DSC) in can be repa- rameterized and reformulated as follows:
log det (I+ oZ + 7 Zl ZeC + B.r (Cv)
min 0.
L(O,
To strengthen the block-diagonal structure of self-expressive matrix, choose the block-diagonal
regularizer (Lu et al. 2018) for r(Cx). ). To be specific, given the data affinity Ag, which is induced by default as Av = ([Cw + (CT)) I), the block diagonal regularizer is defined as:
r (Cw) == ||
(10)
where || is the sum of the k smallest eigenvalues of the Laplacian matrix of the affinity
Ay
Consequently, the parameters in O and y of reparameterized PRO-DSC can be trained by Stochastic Gradient Descent (SGD) with the loss function L(O, W) defined in (9) For clarity, we summarize the procedure for training and testing our PRO-DSC in Algorithm
Remark 2.
We note that all the commonly used regularizers with extended block- -oock-diagonal property for self- expressxressive model as discussed in (Lu al. 2018) can be used to improve the -diconnaa structure of self-expressive matrix. More interestingly. the specific type of the regularizers is not essential owning the learned structured representation (Please refer to Table for details), and using specific regularizer or not is also not essential since that the SGD-based optimization also induces some implicit regularization, e.g., low-rank (Gunasekar et al. 2017 Arora et al. 2019).
3 EXPERIMENTS
To validate our theoretical findings and to demonstrate the performance of our proposed framework, we conduct extensive experiments on synthetic data (Sec. 3.T) and real-world data (Sec. 3.2). Im- plementation details and more results are provided in Appendices B.1 and B.3 respectively.
II practice, we set diag(Ca (Cx) = prevent trivial solution Cy = I.
'Recall that the number of zero eigenvalues of the Laplacian matrix equals the number of connected components in the graph (von Luxburg 2007

---

Published as a conference paper at ICLR 2025
Algorithm Scalable & Efficient Implementation of PRO-DSC via Differential Programming
Input: Dataset X' Ximin U Uiess batch size Ti,, hyper-parameters a, B, number of iterations T,
learning rate 1)
Initialization: Random initialize the parameters L ④ in the networks h(:: v and f(: ))
Training:
1:
f l......,TT do
2:
Sample a batch X, E ER Dxmo from Xinin # Forward propagation
3:
Compute self-expressive matrix Cs E Ruxxu by Eqs. 6
4:
Compute representations Zb Rddd by Eq. 8
# Backward propagation
5:
Compute gradients: V
0c
Vo
24
8
6:
Update & and θ via: V +- y n V
+ e - Ve
7: end for
Testing:
8:
Compute self-expressive matrix Clest by Eqs.
6 for Neet
9: Apply spectral clustering the affinity Aust
3.1 EXPERIMENTS ON SYNTHETIC DATA
To validate whether PRO-DSC resolves the collapse issue in SEDSC and learns representations with a UoS structure, we first follow the procedure in (Ding et al.] (023) to generate two sets of synthetic data, as shown in the first column of Figure 5 and then visualize Figure ((b)-(e) the learned representations which are obtained from different methods on these synthetic data.
We observe that the SEDSC model overly compress all the representations to closed curve on the hypersphere; whereas with increased weights (i.e., f) of the self-expressive term, the representa- tions collapse to a few points. Our PRO-DSC yields linearized representations lying on orthogonal subspaces in both cases, confirming the effectiveness of our approach. Nevertheless, MLC (Ding al. 2023) yields representations approximately on orthogonal subspaces.
(a) Input Data
(b) SEDSC
SEDSC (r 1)
(d) MLC
(c) PRO-DSC
Figure 5: Visualization Experiments Synthetic Data.
3.2 EXPERIMENTS ON REAL-WORLD DATA
To evaluate the performance of our proposed approach, we conduct experiments on six real-world image datasets, including CIFAR-10. CIFAR-20, 1IFAR-100, ImageNet-Dogs. 15, Tmag-lma 200, and ImageNet- lk, with the pretrained CLIP feature (Radford al. (021). ). and compare to several baseline methods, including classical clustering algorithms, e.g., k- k-means (MacQueen 1967) and spectral clustering (Shi & Malik| 2000), subspace clustering algorithm, e.g., EnSC (You et al. 2016a) and SENet (Zhang al. 2021) deep clustering algorithms, e.g., SCAN (Van Gansbeke al. 2020), TEMI Addllgllou et al. 2023) and CPP (Cuu et al. 2024). and deep subspace clustering algorithms, e.g., DSCNet (Ji al. 2017) and EDESC (Cal et al. 2022)
We measure clustering
*llesse refer Appendix B.3 for the results on other pre-trained models.

---

Published as a conference paper at ICLR 2025
Table 1: Clustering performance Comparison on the CLIP features. The best results are in bold and the second best results are underlined. "OOM" means out of GPU memory.
Method
ACC
CIFAR-I0
NMI
ACC
CIFAR-20
NMI
ACC
CIFAR-100
NMI
ACC
TinylngNer-200 NMI
ACC
ImgNetDoog-
NMI
ACC
ImageNet-Il Ik
NMI
I-means
83.5
84,1
46.9
49.4
52.8
66.8
54.1
73.4
52.7
53.6
53,9
79,8
66.4
SSCOMP
85.5
83.0
61.4
63.4
55.6
69.7
56.7
72.7
25.6
15.9
44.1
74.1
EnSC
95.4
90.3
61.0
68.7
67.0
77.1
64.5
77.7
$7.9
56.0
59.7
83.7
SENet
91.2
82.5
65.3
68.6
67.0
74.7
63.9
76.6
58.7
55.3
53.2
78.1
SCAN
90.3
70.8
56.5
72.7
70.5
54.4
76.8
TEMI
22.6
73.2
79.9
64.0
CPP
96.8
92.3
67.7
20.5
75.4
K2.0
63.4
75.5
83.0
81.5
62.0
82.1
EDESC
84.2
79.3
48.7
49.1
53.1
68.6
51.3
68.8
53.3
47.9
46.5
75.5
DSCNet
78.5
73.6
38.6
45.7
38.2
53.4
62.3
68.3
40.5
30.1
00M
OOM
PRO-DSC
97.2a022
92.8ea.4
716211
73.2a98
77.3
$2.4e0.
69.8
80.5em
84.0
$1,2=08
65.0
$3,4
performance using clustering accuracy (ACC) and normalized mutual information (NMI), and report the experimental results in [ where the results of our PRO-DSC are averaged over 10 trials (with stdd) Since that for most baselines, except for TEMI, the clustering performance with the CLIP feature has not been reported, we conduct experiments using the implementations provided by the authors. For TEMI, we directly cited the results from (Adaloglou et al. 2023).
Performance comparison. As shown in Table I our PRO-DSC significantly outperforms subspace clustering algorithms, e.g., SSCOMP, EnSC and SENet, and deep subspace clustering algorithms, e.g., DSCNet and EDESC. Moreover, our PRO-DSC obtains better performance than the state-of- the-art deep clustering and deep manifold clustering methods, e.g.. SCAN, TEMI and CPP.
Validation to the theoretical results. To validate whether the aligmment emerges and when rep- resentations collapse occurs during the training period, we compute G,, 2 Z, and M, (I (I C,) in mini-batch at different epoch during the training period, and then measure the Gbu, where alignment error via |G,M, M, and the eigenspace correlation via (u,. G.u,le"
u, is the j-th ending eigenvecto of M, for j = 1...., Mg, and plot the eigenvalues of G, and Ma. where is the sample size per mini-batch. Moreover, we also record empirical performance ACC and SRE on CIFAR-10 10 and CIFAR-100 under varying syper-parameters a and y to validate the condition in Theorem 2 to avoid collapse. Experimental results displayed in Figures] and We observe that G, and M, are increasingly aligned and the representations will no longer collapse provided that the parameters are properly set. More details are provided in Section B.2
Evaluation on learned representations. To quantitatively evaluate the effectiveness of the learned representations, run k-means (MacQueen 1967). spectral clustering (Shi & Malik 2000), and EnSC (You et al., (20 on four datasets with three different features: a) the CLIP features, b) the representations learned via CPP, and e) the representations learned by our PRO-DSC. Experimental results are shown in Figure 6 (and more results are given in T. Appendix B.3) We observe that the representations learned by our PRO-DSC outperform the CLIP features and the CPP repre- sentations in most cases across different clustering algorithms and datasets. Notably, the clustering accuracy with the representations learned by our PRO-DSC exceeds 90% on CIFAR-10 10 and 75% on CIFAR- 100, whichever clustering algorithm is used. Besides, the clustering performance is further improved by using the learnable mapping h(: V) indicating a good generalization ability.
100
+SSC
20
28
(a) C1FAR-10
(b) CIFAR- 100
(c) CIFAR-20
(d) TinylmageNet-200
Figure 6: Clustering accuracy with CLIP features and learned representations.
The eigenvectors are sorted according eigenvalues of M, in ascending order.
8

---

Published as a conference paper at ICLR 2025
Sensitivity to haper-parameters. In Figure 2 verify that PRO-DSC yields satisfactory
results when the conditions in Theorem 2 to avoid collapse are met. Moreover, we evaluate the the CLIP features of CIFAR-
performance sensitivity hyper-parameters y and / by experiments 10, CIFAR-100 and l'nylmageNer-200 with varying 7 and 3. In Figure 7 we observe that the clustering performance maintains satisfactory under broad range of y and B
0.02
97.
0.16
0.05
0.08
45.0
760
0.21
96.1
0.08
60.
350
35.
0.18
100
200
300
460
390
500
700
150
250
350
430
350
650
750
500
100 200 300
660
300
600
700
550
(a) CIFAR-10
(b) CIFAR- 100
(c) TinylmageNet
Figure 7: Evaluation on sensitivity to hyper-parameters y and /3 on three datasets.
Time and memory cost. The most time-consuming operations in our PRO-DSC are computing the term involving log d-)(-) and the term || involving eigenvalue decomposition, respectively.
The time complexity for log (-) is (min (m dd))) due to the commutative property of log det(-) function Yu et al. 2020), and the time complexity for || is O(kg)
TO Therefore the overall
time complexity of our PRO-DSC is Okkn + min d) Note that TEMI (Adaloglou et al,
2023) employs H 50 cluster heads during training, adding further time and memory costs and
CPP (Chu et al. 2024) involves computing log det(-) for n& + 1 times, leading to complexity
((1) 1) min (m d) The computation time and memory costs shown in Table for which all the experiments are conducted on a single NVIDIA RTX 3090 GPU and Intel Xeon Platinum 8255C CPU. We read that our PRO-DSC significantly reduces the time consumption, particularly
for datasets with large number of clusters.
Table 2: Comparison time (s) and memory cost (MiB). "OOM" means out of GPU memory.
Methods
Complexity
CIFAR-10
CIFAR-
ImageNet- 1k Memory
Time
Memory
Time
Memory
Time
SEDSC TEMI CPP PRO-DSC
O(N4d) OllInyd)
0OM
0OM
0OM
6.9
1,766
5.1
2,394
262.1
2,858
Ol(ns + mim (
3.5
3,802
7.1
10,374
1441.2
22,433
Olkn min
4.5
2,158
4.0
2,328
90.0
2,335
Table 3: Ablation studies on different loss functions and regularizers.
Loss Term
CIFAR-I0 ACC
CIFAR-100
ImgNetDogs-15
[
[CI
[[C].
NMI
ACC
NMI
ACC
NMI
Regnlarizer Ablaton
56.9
47.7
54.6
60.9
46.7
37.1
69.6
56.4
64.7
71.7
10.5
1.7
97.0
93.0
74.6
80.9
80.9
78.8
v
97.0
92.6
75.2
81.1
81.3
79.1
97.0
92.6
75.2
80.9
80.9
78.8
96.7
91.9
76.4
81.8
81.0
78.8
97.2
92.8
77.3
82.4
84.0
81.2
Ablation study. To verify the effectiveness of each components in the loss function of our PRO- DSC, we conduct a set of ablation studies with the CLIP features on CIFAR-10, CIFAR-100, and ImageNetDDogs-11 15, and report the results in Table where L1 1/2 log det (I a Ze) and Z Cy 1 The absence of the term &, leads catastrophic feature collapse (as demonstrated in Sec. 2.1 whereas without the self-expressive Lz, the model lacks a loss function
L2 =
Ze Z
Foro an N x N matrix, the complexity of computing its & eigenvalues by Lanczos algorithm is O(kN?) and the complexity of computing its det(-) is (NN)).

---

Published as a conference paper at ICLR 2025
for learning the self-expressive coefficients. In both cases, clustering performance drops signifi- cantly. More interestingly, when we replace the block diagonal regularizer || K with ||C||2. ||C||=,
and ||C||| even drop the explicit regularizer r(-), the clustering performance still maintains sat- isfactory. This confirms that the choice of the regularizer not essential owning to the structured representations learned by our PRO-DSC.
RELATED WORK
Deep subspace clustering. tackle with complex real world data, a number of Self-Expressive
Deep Subspace Clustering (SEDSC) methods have been developed in the past few years, e.g.. (eng
ctt al. 2016 2018
Ji et al. 2017: Zhou et al. 2018 Zhang et al., 2019a b. Dang et al. 2020 Peng
et al. 2020 Lv et al. 2021 1
Cai et al. [022] Wang et al. 2023b). The key step SEDSC is to adopt
a deep learning module to embed the imput data into feature space. For example, deep autoencoder
network is adopted in (Peng et al. 2016 2018), deep convolutional autoencoder network is used in (Ji et al. 2017 Zhou et al. 2018 Zhang et al. 2019a). Unfortunately, as pointed out in (Haeffele) al. 2021). l), the existing SEDSC methods suffer from a catastrophic feature collapse and there is no evidence that the learned representations align with a UoS structure. To date, however, a principled
deep subspace clustering framework has not been proposed.
Deep clustering, Recently, most of state-of-the-art deep clustering methods adopt a two-step proce- dure: at the first step, self-superviedd learning based pre-training, c.g., SimCLR Chen et al. 2020a), MoCo (He et al. (222)) B YOL (Grill et al. 2020) and SWAV (Caron et al.. 2020), is adopted to learn the representations; and then deep clustering methods are incorporated to refine the representations, via, e.g., pseudo-labeling
(Caron et al.] 2018 Van Gansbeke et al., 2020; Park et al., [2021] Niu al. 2022), cluster-level contrastive learning (Li et al. (021). local and global neighbor match- ing (Dang et al. 202T), graph contrastive learning (Zhong et al., 202 T, self-distillation (Adaloglou ctt al. (023). Though the clustering performance has been improved remarkably, the underlying geometry structure of the learned representations is unclear and ignored.
Representation learning with a UoS structure. The methods for representation learning that favor
UoS structure are pioneered in supervised setting, e.g., (Lezama et al. 2018 Yu et al., (020). In (Lezama et al.] 2018)) a nuclear norm based geometric loss is proposed to learn representations that lie on union of orthogonal subspaces; in Yu al., 2020), a principled framework called Maximal Coding Rate Reduction (MCR²) is proposed to learn representations that favor the structure of union of orthogonal subspaces (Wang et al. 2024]. More recently. the MCR² framework is modified to develop deep manifold clustering methods, e.g., NMCE (Li et al., 2022), MLC (Ding et al. 2023) and CPP (Chu et al. 2024). In (Li al. 2022), the MCR framework combines with constrastive learning to perform manifold clustering and representation learning; in (Ding et al. (202)). the MCR* 2 framework combines with doubly stochastic affinity learning to perform manifold linearizing and clustering; and in (Chu et al.] 2024). the features from large pre-trained model (e.g., CLIP) are adopted to evaluate the performance of (Ding et al. 2023 While the MCR² framework has been modified in these methods for manifold clustering, none of them provides theoretical justification to yield structured representations. Though our PRO-DSC shares the same regularizer defined in Eq. (3) with MLC (Ding et al. 2023), we are for the first time to adopt it into the SEDSC framework to attack the catastrophic feature collapse issue with theoretical analysis.
CONCLUSION
We presented a Principled fRamewOrk for Deep Subspace Clustering (PRO-DSC), which jointly learn structured representations and self-expressive coefficients. Specifically, our PRO-DSC incor- porates an effective regularization into self-expressive model to prevent the catastrophic representa- tion collapse with theoretical justification. Moreover, we demonstrated that our PRO-DSC is able to leam structured representations that form a desirable UoS structure, and also developed an efficient implementation based on reparameterization and differential programming. We conducted extensive experiments on synthetic data and six benchmark datasets to verify the effectiveness of our proposed approach and validate theoretical findings.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like to thank the constructive comments from anonymous reviewers. This work supported by the National Natural Science Foundation of China under Grant 61876022.
ETHICS STATEMENT
In this work, we aim to extend traditional subspace clustering algorithms by leveraging deep learning techniques enhance their representation learning capabilities. Our research does involve any human subjects, and we have carefully ensured that it poses no potential risks or harms. Additionally, there are no conflicts of interest, sponsorship concerns, or issues related to discrimination, bias, or fairness associated with this study. We have taken steps to address privacy and security concerns, and all data used comply with legal and ethical standards. Our work fully adheres to research integrity principles, and no ethical concerns have arisen during the course of this study.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our work, we have released the source code. Theoretical proofs of the claims made in this paper are provided in Appendix A and the empirical validation of these theoretical results is shown in Figures 2 with further detailed explanations in Appendix [B.2] All datasets used in our experiments are publicly available, and we have provided comprehensive de- scription of the data processing steps in Appendix [B]]] Additionally, detailed experimental settings and configurations are outlined in Appendix B.1 to facilitate the reproduction of our results.
REFERENCES
Nikolas Adaloglou, Felix Michels, Hamza Kalisch, and Markus Kollmann. Exploring the limits of deep image clustering using pretrained models. In British Machine Vision Conference, pp- 297-299, 2023.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 02:7411-74221 2019.
Laurent Bako and René Vidal. Algebraic identification of MIMO SARX models. In International Workshop on Hybrid Systems: Computation and Control, pp. 43-57, 2008.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. Advances in Neural Information Processing Systems, pp. 153-160, 2006.
Jinyu Cai, Jicong Fan, Wenzhong Guo, Shiping Wang, Yunhe Zhang, and Zhao Zhang. Efficient deep embedded subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 21-30, 2022.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In European Conference on Computer Vision, pp. 132-149, 2018.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances Neural Information Processing Systems, 33:9912-99244 2020.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the JEEE/CVF International Conference on Computer Vision, pp. 9650-9660, 9660, 2021.
Jianlong Chang, Gaofeng Meng, Lingfeng Wang, Shiming Xiang, and Chunhong Pan. Deep self- evolution clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4); 809-823, 2018.
11

---

Published as a conference paper at ICLR 2025
Guangliang Chen and Gilad Lerman. Spectral curvature clustering (SCC). International Journal of Computer Vision, 81(3):317-330 2009.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, pp. 1597-1607, 2020a.
Ying Chen, Chun- Guang Li, and Chong You. Stochastic sparse subspace clustering. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4155-4164,
2020b.
Tianzhe Chu, Shengbang Tong, Tianjiao Ding, Xili Dai, Benjamin David Haeffele, René Vidal, and Yi Ma. Image clustering via the principle of rate reduction the age pretrained models. In International Conference Learning Representations, 2024.
Joao Paulo Costeira and Takeo Kanade. multibody factorization method for independently moving objects. International Journal of Computer Vision, 29:159-179, 1998.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26:2292-2300, 2013.
Zhiyuan Dang, Cheng Deng, Xu Yang, and Heng Huang. Multi-scale fusion subspace clustering using similarity constraint. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6657-6666, 2020.
Zhiyuan Dang. Cheng Deng, Xu Yang. Kun Wei, and Heng Huang, Nearest neighbor matching for deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13693-13702, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142. 2012.
Tianjiao Ding, Shengbang Tong, Kwan Ho Ryan Chan, Xili Dai, Yi Ma, and Benjamin D. Haeffele. Unsupervised manifold linearizing and clustering. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5450-5461 October 2023.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 2790-2797, 2009.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applications.
IEEE Transactions on Puttern Analysis and Machine Intelligence, 35(11):275-2781. 2013.
Maryam Fazel, Haitham Hindi, and Stephen P Boyd. Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices. In American Control Conference, volume 3, pp. 2156-2162, 2003.
Martin A Fischler and Robert Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24 (6):381-395, 1981.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a approach to self-supervised learning, Advances in Neural Information Processing Systems, 33:21271 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Sre- bro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
12

---

Published as a conference paper at ICLR 2025
Benjamin D Haeffele, Chong You, and René Vidal. A critique of self-expressive deep subspace clustering. In International Conference on Learning Representations, 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9729-9799 9738, 2020.
Kaiming Hc, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked au- toencoders scalable vision learners. In Proceedings the Vision and Pattern Recognition, pp. 16000-16009, 2022.
the IEEE/CVF Conference Computer
Jeffrey Ho, Ming Hussng Yang. Jongwoo Lim, Kuang- Chin Lee, and David Kriegman. Clustering appearances of objects under varying illumination conditions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 11-18, 2003.
Wei Hong, John Wright, Kun Huang, and Yi Ma. Multiscale hybrid linear models for lossy image representation. IEEE Transactions Image Processing, 15)3)):365-3361, 2006.
Zhizhong Huang, Jie Chen, Jumping Zhang, and Hongming Shan. Learning representation for clus- tering via prototype scattering and positive sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(6):7509-7524 2023.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and Ian Reid. Deep subspace clustering networks. Advances in Neural Information Processing Systems, pp. 24-33, 2017.
Yuheng Jia, Jianhong Cheng, Hui LIU, and Junhui Hou, Towards calibrated deep clustering network. In International Conference on Learning Representations, 2025.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
José Lezama, Qiang Qiu, Pablo Musé, and Guillermo Sapiro. OLE: Orthogonal low-rank embedding plug and play geometric loss for deep learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8109-8118 $118, 2018.
Chun-Guan Li, Chong You, and René Vidal. Structured sparse subspace clustering: A joint affinity learning and subspace clustering framework. IEEE Transactions Image Processing, 26(6): 2988-3001, 2017.
Chun-Guang Li, Chong You, and René Vidal. On geometric analysis of affine sparse subspace clustering. IEEE Journal Selected Topics in Signal Processing, 12(6):1220-1533, 2018.
Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive cluster- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8547-8555, 2021.
Zengyi Li, Yubei Chen, Yann LeCun, and Friedrich T Sommer. Neural manifold clustering and embedding. arXiv preprint arXiv:2201.10000 2022.
Derek Lim, René Vidal, and Benjamin D Haeffele. Doubly stochastic subspace clustering, arXiv preprint arXiv:2011. 148559 2020.
Guangean Liu, Zhouchen Lin, and Yong Yu. Robust subspace segmentation by low-rank represen- tation. In International Conference on Machine Learning, pp. 663-670, 2010.
Xin Liu, Zhongdao Wang. Ya-Li Li, and Shengjin Wang. Self-supervised learning via maximum entropy coding. Advances in Neural Information Processing Systems, 35:34091-34105, 2022.
Canyi Lu, Hai Min, Zhong-Qi Qiu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. In European Conference on Computer Vision, pp. 347-360, 2012.
13

---

Published as a conference paper at ICLR 2025
Canyi Lu, Jiashi Feng, Zhouchen Lin, Tao Mei, and Shuicheng Yan. Subspace clustering by block diagonal representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(2): 487-501, 2018.
Juncheng Lv, Zhao Kang, Xiao Lu, and Zenglin Xu. Pseudo-superiie deep subspace clustering. IEEE Transactions Image Processing, 30:5252-52663 2021.
Yi Ma, Harm Derksen, Wei Hong, and John Wright. Segmentation of multivariate mixed data via lossy coding and compression. IEEE Transactions Pattern Analysis and Machine Intelligence, 1969):144-1166, 2007.
MacQueen. Some methods for classification and analysis of multivariate observations. In Proceed- ings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp. 281-297, 1967.
Ryan McConville, Raul Santos-Rodriguee Robert J Piechocki, and lan Craddock. N2d:(not too) deep clustering via clustering the local manifold of autoencoded embedding. In Proceedings of the International Conference on Pattern Recognition, pp. 5145-5152, 2021.
Brian McWilliams and Giovanni Montana. Subspace clustering of high dimensional data: a predic- tive approach. Data Mining and Knowledge Discovery, 28(3):736-772, 2014.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In International Conference on Machine Learning, pp. 807-814, 2010.
Maria-Elena Nilsback and Andrew Zisserman, Automated flower classification over a large number of classes. In Proceedings of the Indian Conference on Computer Vision, Graphics & Image Processing, pp. 722-729, 2008
Chuang Niu, Hongming Shan, and Ge Wang. SPICE: Semantic pseudo-labeling for image cluster- ing. IEEE Transactions on Image Processing, 31:7264 7278, 2022.
Foivos Ntelemis, Yaochu Jin, and Spencer A Thomas. Information maximization clustering via multi-view self-labelling. Knowledge-Band Based Systems, 250:109042, 2022.
Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy V. Vo, Mare Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel HAZIZA, Francisco Massa, Alaaeldin El-Nouby, Mido Assran, Nicolas Ballas, Wojciech Galuba, Russell Howes, Po- Yao Huang, Shang- Wen Li, Ishan Misra, Michael Rabbat, Vasu Sharma, Gabriel Synnaeve, Hu Xu, Herve Jegou, Julien Mairal, Patrick Labatut, Ar- mand Joulin, and Piotr Bojanowski. Dinov2: Learning robust visual features without supervision. Transactions on Machine Learning Research, 2024.
Sungwon Park, Sungwon Han, Sundong Kim, Danu Kim, Sungkyu Park, Seunghoon Hong, and Meeyoung Cha. Improving unsupervised image clustering with robust learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 12278- 2021.
Vishal M Patel and René Vidal. Kernel sparse subspace clustering. In Proceedings of the IEEE International Conference on Image Processing, pp. 9849-2853, 2014.
Vishal M Patel, Hien Van Nguyen, and René Vidal. Latent space sparse subspace clustering. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 225-232, 2013.
Vishal M Patel, Hien Van Nguyen, and René Vidal. Latent space sparse and low-rank subspace clustering. IEEE Journal of Selected Topics in Signal Processing. 944:6991701, 2015.
Xi Peng, Shijie Xiao, Jiashi Feng, Wei-Yun Yau, and Zhang Yi. Deep subspace clustering with sparsity prior. In International Joint Conference on Artificial Intelligence, pp. 1925-1931, 2016.
Xi Peng, Jiashi Feng, Shijie Xiao, Wei-Yu Yun Yau, Joey Tianyi Zhou, and Songfan Yang. Structured autoencoders for subspace clustering. IEEE Transactions on Image Processing, 27(1))5077- 5086, 2018
14

---

Published as a conference paper at ICLR 2025
Xi Peng, Jiashi Feng, Joey Tianyi Zhou, Yingjie Lei, and Shuicheng Yan. Deep subspace clustering. IEEE Transactions on Neural Networks and Learning Systems, 31(12):5509-333 -5221,,,,,-,,,,,,, 2020.
Daniel Pimentel-Alarcon and Robert Nowak. The information-theoreiic requirements of subspace clustering with missing data. In International Conference Machine Learning, pp. 802-810, 2016.
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, 2021.
pp.
Shankar Rao, Roberto Tron, René Vidal, and Yi Ma. Motion segmentation in the presence of out- lying, incomplete, or corrupted trajectories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(10)) 2010.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8888))88 2000.
Mahdi Soltanolkotabi and Emmanuel Candes. geometric analysis of subspace clustering with outliers. Annals of Statistics, (0(4):2195-2233) 2012.
Manolis Tsakiris and René Vidal. Algebraic clustering of affine subspaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(2):482-489, 2017.
Manolis Tsakiris and René Vidal. Theoretical analysis of sparse subspace clustering with missing entries. International Conference on Machine Learning, pp. 4975 2018.
Paul Tseng. Nearest q-flat to m points. Journal of Optimization Theory and Applications, 105(1): 249-252, 2000.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(1 (11), 2008.
Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis. Mare Proesmans, and Luc Van Gool. SCAN: Learning to classify images without labels. In European Conference on Com- puter Vision, pp. 268-2228800 285, 2020.
René Vidal. Identification of PWARX hybrid models with unknown and possibly different orders. In Proceedings of the American Control Conference, pp. 547-552, 2004.
René Vidal, Yi Ma, and Shankar Sastry. Generalized Principal Component Analysis (GPCA). IEEE Transactions on Puttern Analysis and Machine Intelligence, 27(12):1-15, 2005.
René Vidal, Roberto Tron, and Richard Hartley. Multiframe motion segmentation with missing data using PowerFactorization, and GPCA. International Journal of Computer Vision, 79(1)855-055, 2008.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395 2007.
Libin Wang, Yulong Wang, Hao Deng, and Hong Chen. Attention reweighted sparse subspace clustering. Pattern Recognition, 139:109433 2023a.
Peng Wang, Huikang Liu, Druv Pai, Yaodong Yu, Zhihui Zhu, Qing Qu, and Yi Ma. A global geometric analysis of maximal coding rate reduction. In International Conference on Machine Learning, 2024.
Shiye Wang, Changsheng Li, Yanming Li, Ye Yuan, and Guoren Wang. Self-supervised information bottleneck for deep milti-view subspace clustering. IEEE Transactions Image Processing. 32: 1555-1567, 2023b.
Yu- Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. Journal of Machine Learning Research, 17(12):1-4) 2016.
15

---

Published as a conference paper at ICLR 2025
Lai Wei, Zhengwei Chen, Jun Yin, Changming Zhu, Rigui Zhou, and Jin Liu. Adaptive graph convolutional subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 62626622666622 6221, 2023.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprini arXiv: / 170.007477 2017.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning, pp. 478 487, 2016.
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 5147-5156, 2016.
Chong You, Chun- Chun-Guang Li, Daniel Robinson, and René Vidal. Oracle based active set algorithm for scalable elastic net subspace clustering. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 3928-3937, 2016a.
Chong You, Daniel Robinson, and René Vidal. Scalable sparse subspace clustering by orthogonal matching pursuit. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3918-3927, 2016b.
Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, and Yi Ma. Learning diverse and discriminative representations via the principle of maximal coding rate reduction. Advances in Neural Information Processing Systems, 33:9422- 9434, 2020.
Pengxin Zeng, Yunfan Li, Peng Hu, Dezhong Peng, Jiancheng Lv, and Xi Peng. Deep fair cluster- ing via maximizing and minimizing mutual information: Theory, algorithm and metric. In Pro- ceedings of the IEFE/CVF Conference on Computer Vision and Pattern Recognition, pp. 23986 23995, 2023.
Hongjing Zhang and Ian Davidson. Deep fair discriminative clustering. arXiv preprint arXiv:2105. 14146, 2021.
Junjian Zhang, Chun-Guang Li, Chong You, Xianbiao Qi, Honggang Zhang, Jun Guo, and Zhouchen Lin. Self-supervised convolutional subspace clustering network. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5473-5482, 2019a.
Shangzhi Zhang, Chong You, René Vidal, and Chun Mhun-Guang Li. Learning self-expressive network for subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12393-12403, 2021.
Teng Zhang, Arthur Szlam, and Gilad Lerman. Median k-flats for hybrid linear modeling with many outliers. In JEEF/CVF International Conference on Computer Vision Workshops, pp. 234-241, 2009.
Tong Zhang, Pan Ji, Mehrtash Harandi, Wenbing Huang, and Hongdong Li. Neural collaborative subspace clustering. In International Conference on Machine learning, pp. 7384-7393, 2019b.
Chen Zhao, Chun-Guang Li, Wei He, and Chong You. Deep self-expressive learning. In The First Conference on Parsimony and Learning, volume 234, pp. 228-247, 2024.
Huasong Zhong, Jianlong Wu, Chong Chen, Jianqiang Huang, Minghua Deng, Liqiang Nie, Zhouchen Lin, and Xian-Sheng Hua. Graph contrastive clustering. In Proceedings of the JEEF/CVF International Conference on Computer Vision, pp. 9233, 2021.
Pan Zhou, Yunqing Hou, and Jiashi Feng. Deep adversarial subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2018.
16

---

Published as a conference paper at ICLR 2025
SUPPLEMENTARY MATERIAL FOR "EXPLORING A PRINCIPLED FRAMEWORK FOR DEEP SUBSPACE CLUSTERING"
The supplementary materials divided into three parts. In Section A present the proofs of our theoretical results. In Section B
we present the supplementary materials for experiments, including empirical validation on our theoretical results (Sec. B.2). and more
experimental details (Sec. B.
experimental results (Sec. B.3 In Section C PRO-DSC.
we discuss about the limitations and failure cases of
A PROOFS OF MAIN RESULTS
As preliminary, start by introducing lemma from (Haeffele al. 2021 and provide its proof for the convenience of the readers.
Lemma Haeffell et al. 2021). The rows of the optimal solution Z for problem 2 are the eigen- vectors that associate with the smallest eigemvalues of (I CI - C)
Proof. We note that:
- ZCI = TT (210)))))) -- Σ C) - 1=1
where z00) is the 7th row of Z, thus problem 2 is reformulated as:
(I C) +B.
min (209) S
2
(11)
s.t. Z N.
Without loss of generality, the magnitude of each row of is assumed to be fixed, i.e., ||
Ta i l...., where Md 21=1 N. Then, the optimization problem becomes:
[I C)-C C) (T) + + r(C)
min (2(0)d
(12)
s.t.
|| (0) 1
i = I....,d.
The Lagrangian of problem
d [((2(0) C, (1) =
(1) (- + (
vs (1 11 Ti),
(13)
where {vi] are the Lagrangian multipliers. The necessary conditions for optimal solution are:
V 20 C z(0 CI + (1) 0,
(14)
|| = T., i=
which implies that the optimal solutions 2 are eigenvectors of (I - (C
By further considering the objective functions, the optimal solution 2 should be the eigenvectors
w.r.t the smallest eigenvalues of (I (I-C) (I-)( for all i (1....,d) d). The corresponding optimal
value is 1 Amin (I-C E
+ rCC) N Amin (I-C) B
which is irrelevant to {-
Therefore, we conclude that the rows of optimal solution Z to problem are eigenvectors that associate with the smallest eigenvalues of (I CI - C)
17

---

Published as a conference paper at ICLR 2025
Lemma A1. Suppose that matrices A, A and B can be diagonalized simultaneously by E O(n), where (n)) is an orthogonal group.
Ruxn are symmetric, then AB BA if and only if
Now we present our theorem about the optimal solution of problem PRO-DSC in with its proof.
Theorem 1. Denote the optimal solution of PRO-DSC in 4 as Ze, C+), then G. and M, share eigenspaces, where G == Z Z., M, = (I CI - C.)", iee, G. and M, can be diago- nalized simulhaneously by U O(N) where (NN) an orthogonal matrix group.
Proof. We first consider the subproblem of PRO-DSC problem in 4 with respect to Z and prove that for all C E R N the corresponding optimal Z.,c satisfies G..c. MG,cc, where G.Cc = Z.C M. = (I - (I C implying that G. and M share eigenspace. Then, will demonstrate that G. and M, share eigenspace.
The subproblem with respect to Z is reformulated into the following semi-definite program:
min Ge
log det (I +GGc) + tr(G.M)
2
(15)
Gc = 0, tr(Gc) N,
which has the Lagrangian as:
LGGc, A. = log det (I aGc) ? tr(GcM) - trrrttr(aaa) (tr)))
- N). (16)
where scalar and N N symmetrie matrix A Lagrange multipliers.
The KKT conditions is:
- -I+ aG. 2 A. + 3 I
(17)
2
G.
(18)
tr(G.,c) NN,
(19)
A. 2 O,
(20)
A,G.
(21)
which are the sufficient and necessary condition for the global optimality of the solution G.
From Eqs. 18
20 and 21 we have that A,G.cc G.ccA, = A.G.c - (A.G.,c)
20
G. share eigenspace. By eigenvalue decomposition A. QAa,Q Q G. QAo where AA, AG.. diagonal matrices, have:
O, implying that A. and
2 QAA. Q -aQ(I aAG. + + M MM+u.l - Q + + + QT,
(22)
(23)
where the first equality from Eq. 17 Since that 2A +a (a(I+aAG,,c)-11 is a diagonal matrix, yM + I can be diagonalized by Q. other words, for VM E S problem (15). M will share eigenspace with the corresponding optimal solution G.C. Next, denote (Z., C.) the optimal solution of problem (4). C == {Z 2 N} as the feasible set and f(..-) as the objective function. Since that Z. arg min f(Z,C.) otherwise contradicts with the optimality of
(Z., C.), we conclude that G, and M, share eigenspace, where M, = C.)(I C.)
Theorem 2. Suppose that and M are aligned the same eigenspaces and a
Xmav atmin # . then we have that: a) rank Z.) = min(d, Min(d,N), N), and b) the singular val- OZ.
(8)
7 +v. for all I,..,, min miinnd (d, NY. where Z, and vs are the primal optimal
solution and dual optimal solution, respectively.
18

---

Published as a conference paper at ICLR 2025
Proof. Since 1 ZC Tr (2- and 1 = -Tr(Z' 2). problem (5)
is equivalent to:
1 log det (T+ + ? TrGMM)
min
G 2
(24)
Tr(G) N,
where G = z Z and M = -1-
Since that G' and M have eigenspaces aligned, have G and M diagonalized simultaneously by an orthogonal matrix U. i.e., G = UAGU", .M = UAM Therefore, problem (24) can be transformed into the eigenvalue optimization problem follows:
(i.(d.N)
log(1 x 2x MM
min (.) Timl
(A
2
(25)
min(d.))
s.t.
Σ
2 = N,
A 20, for all i i= I..... min N,,
where ( (miinddNN)) are the diagonal entries of Am and ( G (mi) } are the diagonal entries of Ag. Surprisingly, problem (25) a convex optimization problem. Thus, the KKT condition is sufficient and necessary guarantee for the global minimizer.
M
The Lagrangian of problem 25 is:
C ((1x))
(d.N) (4) Ji=1
{m) (d.N)
/1) =
(d,
min(d.N)
log(1 + ax + 2 AM - m +
N).
(26)
2
where 2 0, = 1..... min,d.N] and v are the Lagrangian multipliers. The KKT conditions are as follows:
L= 0,
Vi = 1, 1,...,,m. min(d, (d, N}.
(27)
A 20,
Vi = 1=:....,,mnff (in N).
(28)
min (d.N)
Σ
(6) N,
(29)
Uix
Vi 1, l,... min [d,]d N}.
(30)
Ps. G. = 0,
Vi = min(d, [nn N}.
(31)
Then, the stationary condition in (77 is equivalent to:
2 v. + 7
(32)
+ ar
By using Eqs.
28 and 30
32
up with the following cases:
Mix > 0 + G. = 0. 1
1
- <0,
(33)
V. + +
1
1
Mis = 0. (1)
>0.
(34)
V, + 72
a
From the above two cases, we conclude that:
G. max (0.
1
(35)
ve + 7>
a
19

---

Published as a conference paper at ICLR 2025
where satisfies:
minfd.N7
Σ
max O.
a = N.
(36)
Ue + 7
(6) M
Given that 7 (a--2))) D+)/Amax Therefore, for the optimal solution Z, of problem (5) we conclude that: rank (Z.) min NJ and the singular values Z.
Amax (M), we have
0 for all 1,..., min N)-
(4)
7AM a for all i min N).
Note that, the results we established just above rely on a condition 7m (M) a V, where the P. is the optimal Lagrangian multiplier, which is set as a fixed value related to a, Y and Xmax (M). Next, we will develop an upper bound for 24 and justify the fact that we ensure v, to satisfy the condition y) < a V4 by only adjusting the hyper- parameters a and
In Eq. 360. we can easily find an upper bound 2/ as:
min (d.N)
min Nd,
min Nd,N)
N
max 0,
S
(37)
U4 + 7AM
(4)
V + 7Ymin (M)
V4
Mmmin (M);
(38)
min(d,N)
Therefore, we can find a tighten bound between a 14 and 7mmax (M) as:
a
a²
Amax (M)
min (M) S a Vx:
(39)
min 1}
+ min [N.1
which means that the condition of >mmax (M) < a v. can be reformed as:
1
a
(40)
Amax (M) a + min 4
N
Remark We notice that 25 reverse water-filling problem, where the water level is controlled by 1/a, as shown in Figure A.I When G and M have eigenspaces aligned and
7 < (a /max (M), we have rank Z.) min(d, N) and ((i for all s min(d, N).
When 7 2 (a- v/)/ Amax M non-zero A first disappears for the larger (1)
XM
1/a
Figure A.1: Illustration of the optimal solution for problem transformed into classical reverse water-filling problem.
25
The primal problem can be
Theorem 3. Suppose that the sufficient conditions prevent catastrophic feature collapse sat- isfied. Without loss of generality, we further assume that the columns in matrix are arranged into k blocks according certain N N permutation matrix I, i.e., Z [Z,, Zz, Zz). Then the
20

---

Published as a conference paper at ICLR 2025
condition for that PRO-DSC promotes the optimal solution Z., C.) be desired structure (i.e., Z Z, and C, are block dock-aiag,,,a), is that (1-C)( (I-C)(I- C) G GO) + 0, where
G11
G = Diag (G11, G22. ... GuR)
Gkk
and G5 is the block Gram matrix corresponding to Zz-
Proof. We begin with the analysis to the first two terms of the loss function 2 = L1 + 7L2, where
L == log det (I + a (T)) ZT) =
2 log det I + aa))
2
1
ZT ZTT CT 2 211 --|I TI (II--C(I-
1
C2 2
since that I IT= =I Thus, we have:
E - Tr (C(1-))((-))))) - log det + aG),
(41)
which is a convex function with respect to (w.r.t) G and C, separately. By the property of convex function w.r.t C, have:
Č(G,C) 2 GG c*)+ (eddd G-
,G
Cn
where C = Diag (C11, C2 CER)
with the blocks associating to the
C
partition of Z = [z, Zz. Zn}. Since that
( = 0 due to the comple-
mentary between G* and I - -C*, we have:
[(G 2 C*) ()+ G G-G).
G²) G-G") is easy to see that if (II-C) G
0, then we will have:
LG C) 2 "(G,,C")
(42)
where the equality holds only when - G C C Furthermore, if the regularizer r(-) satisfies the extended block diagonal condition as defined in (Lu et al. 2018), then we have that r(C) > r(C"), where the equality holds if and only C C Therefore, we have:
C(G,C)= ((G + (()))(())))))))))))))))))
LG"" + =[G""
(43)
r(C) promotes the Thus we conclude that minimizing the loss function L(G, C¹) B optimal solution (G., C.) to have block diagonal structure.
We note that the Gram matrix being block-diagonal, i.e., G. = G", implies that Z_ Z = 0 for all 51 j2 < k, which is corresponding the subspaces associated to the blocks Z., orthogonal to each other.
21

---

Published as a conference paper at ICLR 2025
B EXPERIMENTAL SUPPLEMENTARY MATERIAL
B.I EXPERIMENTAL DETAILS
B.1.1 SYNTHETIC DATA
As shown in Figure Sa (top row), data points are generated from two manifolds. The first manifold (colored in purple) generated by sampling 100 data points from
cos ( sin (5p)) cos yp
a
cos (5 sin (54) sin yp +,,
(44)
sin ( sin (5p))
where yp is taken uniformly from [0, 2T] and E ~ .N (0, 0.051a) is the additive noise. The second manifold (colored in blue) is generated by sampling 100 data points from a Gaussian distribution
N (10,0, 1]" 0.0513). To further test more complicated cases, we generate the second manifold by sampling 50 data points from a Gaussian distribution / (10, (0 0.051,) and 50 data points from another Gaussian distribution / (10, 10,00,-1] -1] .0.05I3)
shown in Figure 5a (bottom row).
In PRO-DSC the learnable mappings h(: : L and (-: ①) are implemented with two MLPs with Rectified Linear Units (ReLU) (Nair & Hinton 2010) as the activation function. The hidden dimen- sion and output dimension of the MLPs are set to 100 and 3, respectively. We train PRO-DSC with batch-size ni = 200, learning rate = 10-3 for 1000 epochs. We set 7 0.5, 3 1000, and
3
0.1-200
We use DSCNet (Ji et al. 2017) as the representative of the SEDSC methods. In Figure 5b 1 for both cases, whereas in Figure 5c is set to 5 and 100 for the two cases, respectively. The encoder and decoder of DSCNet are MLPs of two hidden layers, with the hidden dimensions being set to 100 and 3, respectively. We train DSCNet with batch-size n, 200, learning rate 7 x 10 4 for 1000 epochs.
we set
B. 1.2 REAL-WORLD DATASETS
Datasets description. CIFAR-10 10 and CIFAR-100 are classic image datasets consisting of 50,000 images for training and 10,000 images for testing. They are split into 10 and 100 classes, respec- tively. CIFAR-20 shares the same images with CIFAR-100 while taking 20 super-classes as labels. ImageNet-Dogs consists of 19,500 images of 15 different dog species. Tiny-ImageNei consists of 100,000 images from 200 different classes. ImageNet-Ik is the superset of the two datasets, con- taining more than 1,280,000 real world images from 1000 classes. For all the datasets except for ImageNet-Dogs, we train the network to implement PRO-DSC on the train set and test it on the test set to validate the generalization of the learned model. For ImageNet- have test set, train the network to implement PRO-DSC on the train set and report the clustering performance on the training set. For a direct comparison, we conclude the basic information of these datasets in Table B.1
dataset which does not
To leverage the CLIP features for training, the input images are first resized to 224 with respect to the smaller edge, then center-cropped 224 x 224 and fed into the CLIP pre-trained image encoder to obtain fixed features [D] The subsequent training of PRO-DSC takes the extracted features as input, instead of loading the entire CLIP pre-trained model.
Network architecture and hyper-parameterrs The learnable mappings h(: v and (-; Q) are two fully-con tully-connected layers with the same output dimension d. Following (Chu et al. 2024), for the experiments on real-world data, we stack pre-feature layer before the learnable mappings, which composed of two fully-connected layers with ReLU and batch-norm (Loffe Szegedy 2015).
We train the network by the SGD optimizer with the learning rate set to 17 = 10-4, and the weight decay parameters of f(: and h-; V are set to 10-4 and 10-2 3, respectively.
We use the VIT 1//1 pre-trained model provided by dimensional features.
/CI.PP for 768-
22

---

Published as a conference paper at ICLR 2025
Table B.I: Basic statistical information of datasets. We summarize the information in terms of the data with both the train and test split, as well as the number of classes involved.
Datasets
# Train
Test
Classes
CIFAR-I0
50,000
10,000
10
CIFAR-20
50,000
10,000
20
CIFAR-I00 100
50,000
10,000
100
ImageNet-Dogs
19,500
N/A
15
TinyImageNet
100,000
10,000
200
ImageNet
1,281,167
50,000
1000
Following by (Chu et al. 2024), we warm up training f(:; () by diversifying the features with L1 = log det(1 + a Zo for few iterations and share the weights to h(: v). We set 0.1-ms for all the experiments. We summarize the hyper-parameten for training the network to implement PRO-DSC Table B.2
Table B.2: Hyper-parameters configuration for training the network to implement PRO-DSC with CLIP pre-trained features. Here is the learning rate, dpre is the hidden and output dimen- sion of pre-feature layer, m the output dimension and f. my is the batch size for training, and ## warm-up" is the number of iterations of warm-up stage.
7
dyre
d
#epochs
#warm up
?
/
CIFAR-10
1x10
4096
128
10
1024
200
300/m²
600
CIFAR-20
1x10 4
4096
256
50
1500
600/na
300
CIFAR-10 100
1x10
4096
128
100
1500
200
150/ns
500
ImageNet-Dogg
1x10
4096
128
200
300/m²
Tit
1x10
4096
256
100
1500
200/m²
400
ImageNet
1x10
4096
1024
100
2048
2000
800/mr
MNIST
1x10
4096
128
100
1024
200
700/ng
400
F-MNIST
1x10
1024
128
200
1024
400
50/ns
100
Flowers
1x10
1024
256
200
1024
200
400/TT
200
spectral clustering (Shi & Malik 2000). EnSC YYou et al. 2016aa). SSCOMP Yoou et al. 2016b), and DSCNet (Ji et al. 2017) based transductive learning, evaluate these models directly the test set for all the experiments.
Running other algorithms. Since that k-means (MacQueen] 1967),
For EnSC, we tune the hyper-parameter (1, 10, 20, 20, 100, 200, 400, 800, 1600, 3200} and the hyper-parameter т in T| 1|1 - 112 to balance the & and l norms in {0.9, 0.95, 1} and report the best clustering result.
For SSCOMP, we tune the hyper-parameter to control the sparsity kmax 21, 10, 20, 50, 100, 200} and the residual E (10-1, 10-3 10-6, 1,10 and report the best clustering result.
To apply DSCNet to the CLIP features, we use MLPs with two hidden layers to replace the convolutional encoder and decoder. The hidden dimension of the MLPs are set to 128. We tune the balancing hyper-parameters 7 E {1, 2, 3, 4} and 3 E {1, 5, 25, 50, 75, 100} and train the model for 100 epochs with learning rate 1j equivalent to number of samples in the test data set.
10-4 and batch-size nı
As the performance of CPP evaluated by averaging the ACC and NMI met- rics tested on each batch, we reproduce the results by their open-source imple- mentation and report the results on the entire test set. The authors provide two implementations (see http:s///ttttttaccmmm//aaarrrrrp
main..y and https: / wtt.c/oc.o/eceeeeeee htt.s//iiieieeeeeel///////aaaaaa
efficient py), where optimizes the cluster head and the feature head separately and the other shares weights between the two heads. In this paper, we test both cases and report the better results.
23

---

and repeat experiments for Published as a conference paper at ICLR 2025
For k-means and spectral clustering (including when spectral clustering is used as the fi- nal step in subspace clustering), we repeat the clustering 10 times with different random initializations (by setting Rinntt 10 in scikit-learn) and report the best results.
For SENet, SCAN and EDESC, we adjust the three times, with only the best results are reported.
B.2 EMPIRICAL VALIDATION ON THEORETICAL RESULTS
Empirical Validation on Theorem To validate Theorem I empirically, we conduct experiments on CIFAR- 100 with the same training configurations as described in Section B.1.2 but change the training period to 1000 epochs. For each epoch, we compute G. Z Z, and M, (I Cr) C.) with the learned representations Z₁ and self-expressive matrix C2 in mini-batch of size n2t after the last iteration of different epoch. Then, to quantify the eigenspace alignment of G. and M,. directly plot the alignment error which is computed via the Frobenius norm of the commutator L = || M Go F in mini-batch of size n& during the training period in Figure La We also show the standard deviation with shaded region after repeating the experiments for random seeds. As can be read, the alignment error decreases monotonically during the training period, implying that the eigenspaces are progressively aligned. Moreover, we find the eigenvector {u,} } of Ms by eigenvalue decomposition, where u denotes the j-th eigenvector which are sorted according to the eigenvalues in the ascending order, and calculate the normalized correlation coefficient which defined as (uz, Gou,/1 G l12). Note that when the eigenspace alignment holds, one can verify that:
GRu
{1. 0.
A + G.
(ujs |Guu,
for all j 1,2, ,,2....,Ryy RR.
(45)
=0
As shown in Figure Tb the normalized correlation curves associated to the first d = 128 eigenvec- tors converge to 1, whereas the rest converge to implying the progressively alignment between G. and Mr.
Empirical Validation on Theorem 2 To verify Theorem 2 we conduct experiments CIFAR-10 and CIFAR-100. The experimental setup keeps the same as described in Section B.1.2 In each epoch, we compute G, 2,, Zn and M, (I CI) C.) from Z, and C, in mini-batch after the last iteration, respectively, and then find the eigenvalues of G,, and M,. We display the eigenvalue curves in Figure Tc and [d. respectively. To enhance the clarity of the visualization, the eigenvalues of Ge and M, are sorted in descending and ascending order, respectively. As can be observed, there are min {d, ny} 128 non-zero eigenvalues in G,, approximately being inversely proportional to the smallest 128 eigenvalues of Mg. This results empirically demonstrate for minimizers.
that rank Z.) = min N) and A
+2.
Furthermore, to verify the sufficient condition of PRO-DSC to prevent feature space collapse, we conduct experiments on CIFAR-10 and CIFAR-100 with varying and 7, keeping all the other hyper-parameters consistent with Table B.2 As can be read in Figure [ Theorem 2 is
a² verified since that 7 < Amax( a+ming & I.1 yields satisfactory clustering accuracy (ACC%)
and gubspace-preserving representation enror (SRE%). The satisfactory ACC and SRE confirm a3
that PRO-DSC avoids catastrophic collapse when 7 Amaz(M) c-+min IJJ holds. When 7 >
Amazi (Ma) mmin 11) PRO-DSC yields significantly worse ACC and SRE. There is phase tran- sition phenomenon that corresponds to the sufficient condition to prevent collapse
Empirical Validation on Theorem 3 To intuitively visualize the structured representations learned by PRO-DSC, we visualize the Gram matrices IZ Z and Principal Component Analysis (PCA)
results for both CLIP features and learned representations on CIFAR-10. 'he experimental setup also keeps the same as described in Section B.1.2
The Gram matrix shows the similarities between representations within the same class (indicated by in-block diagonal values) and across different classes (indicated by off-block diagonal values).
12 In experiments, we estimate that Amaze (M.) = 1 and thus the condition reduces to 7 atmin N
24

---

Published as a conference paper at ICLR 2025
Moreover, display the dimensionality reduction results via PCA for the CLIP features and the learned representation of samples from three categories in CIFAR-10. We use PCA for dimension- ality reduction as it performs a linear projection, well preserving the underlying structure.
As can be observed in Figure 3 the CLIP features from three classes approximately lie on different subspaces. Despite of the structured nature of the features, the underlying subspaces not orthog- onal. In the Gram matrix the CLIP feature, the average similarity between features from different classes is greater than 0.6, resulting in an unclear block diagonal structure. After training with PRO- DSC, the spanned subspaces of the learned representations become orthogonal 13 Additionally, the off-block diagonal values of the Gram matrix decrease significantly, revealing a clear block diagonal structure. These visualization results qualitatively verify that PRO-DSC aligns the representations with a union of orthogonal subspaces)
B.3 MORE EXPERIMENTAL RESULTS
B.3.1 MORE RESULTS OF PRO- DSC ON SYNTHETIC DATA
To explore the learning ability of our PRO-DSC, prepare experiments on synthetic data with adding an additional subspace, as presented in Figure B.1
In case 1, we sample 100 points from Gaussian distribution a (V v2' 0, //1 0.0553) and 100 points from NV[I v2" 0, /2l 0.005s).. respectively. We train PRO-DSC with batch- size nh = 300, learning rate 7] = x 10-3 for 5000 epochs and set y 1.3, 3 = 500, a 0.1.300 We observe that our PRO-DSC successfully eliminates the nonlinearity representations and maximally separates the different subspaces.
In case 2. we add a vertical curve
Coos ( sin (5Ø)) cos sin (5 cos (5p)) cos (1 sin (5p)) sin p
+
(46)
from which 100 points sampled, where overlap in the intersection of the two curves. We train PRO-DSC with batch-size n, 200, learning rate 17 10-3 for 8000 epochs and set 7 0.5, 8 500,
(O. 0.05Iz). We use sin(} cos(5:)) to avoid
200 We observe that PRO-DSC finds difficulties to learn representations of data which are located at the intersections of
the subspaces. However, for those data points which are away from the intersections are linearized well.
(a) Case 1: Input data
(b) Case 1: Learned Z (c) Case Input data
(d) Case 2: Learned Z
Figure B.I: Additional results on synthetic data.
B.3.2 EXPERIMENTS WITH BYOL PRE-TRAINING
To validate the effectiveness of our PRO-DSC without using CLIP features, we conduct a fair com- parison with existing deep clustering approaches. Similar most deep clustering algorithms,
The dimension of each subspace is much greater than (see Figure B.4 The 1-dimensional subspaces observed the PCA results are consequence dimensionality reduction. "Please refer Figure B.3 and B.7 for the results on other datasets and the visualization of the hases of each subspace.
25

---

Published as a conference paper at ICLR 2025
divide the training process into two steps. We begin with pre-training the parameters of the back- bone with BYOL (Grill et al. 2020). Then, we leverage the parameters pre-trained in the first stage and fine-tune the model by the proposed PRO-DSC loss function. Specifically, rate v = 0.05 and the batch size n 256. The output feature dimension d is consistent with the setting for training with the CLIP features. Following (Li et al.) [021 Huang et al., 2023), We ResNet-18 as the backbone for the experiments on CIFAR-IO and CIFAR-20, and use ResNet-34 convolution filter of size
set the learning
the backbone for the experiments on other datasets, and and stride 1 to replace the first convolution filter. We use the commonly used data augmentations methods the input images, which are listed as follows:
transforms Sreefffccc-.sannonleeelaeaoollor size, scale= (0.08, 1 transforms htt.:aaooosssaaandonnoorrtoooto. hwa.fformmsRannddmpppp..... (trpa//amnpppytttaaafaaaaoaaoeee htt.://soooomc.oooooottttee (0.4, 0.4, 0.2, 0.1)], p-0.8),
transforms htt.:///ww....aoooooooooocoaeeea (p=
o sigma=(0.1, 2. ), p=1.0)
transforms han.:mppplya. ([transform: CaussianBlur (kernel.size=2))
When re-implementing other baselines, we use the code provided by the respective authors and report the best performance after fine-tuning the hyper-parameters.
We report the clustering results based on BYOL pre-training in Table B.3 As can be read from
Table B.3 our PRO-DSC outperforms all the deep clustering baselines, including CC (L. et al.
2021), GCC (Zhong et al. 202I). NNM (Dang et al. 2021), SCAN (Van Gansbeke et al. 2020) NMCE (Li al. 2022), IMC-SWAV (Ntelemis et al. 2022 and MLC (Ding et al. 2023).
Table B.3: Clustering performance comparison on BYOL pre-training, The best results are in bold font and the second best results are underlined. Performance marked with "*" is based on our re-implementation.
CIFAR-10
CIFAR-20
CIFAR-100
TinyImgNet-200
ImgNeiDogs- 15
Method
ACC
ACC
NMI
ACC
k-meins
22.9
8.7
13.0
8,4
9.2
23.0
2.5
6.5
10.5
5.5
SC
24.7
13.6
7.0
6.3
CC
79.0
70.5
42.9
43.1
26.9*
48.1
14.0
34.0
42.9
44.5
GOC
85.6
76.4
47.2
47.2
28.2*
49.9*
13.8
34,7
52.6
49.0
NNM
SCAN
88.3
79.7
50.7
48.6
34,3
55.7
29.6*
30.3*
NMCE
89.1
81.2
53.1
52.4
40.0"
$3,9*
21.6
40.0"
39.8
39.3
IMC-SWAV
89.7
81.8
51,9
$2.7
45.1
67.5
28.2
52.6
MLC
92.2
85.5
$8.3
39.6
49.4
68.3
28.2*
$2.2
21.0
68.3*
PRO-DSC
93.0=0.s
B.3.3 MORE EXPERIMENTS ON CLIP, DINO AND MAE PRE-TRAINED FEATURES
Clustering learned representations. To quantitatively validate the effectiveness of the struc- tured representations learned by PRO-DSC, we illustrate the clustering accuracy of representations learned by various algorithms in Figure Here, compared with the representations learned from SEDSC methods, we additionally conduct experiments on DSCNet (Ji et al. 2017) and report the performance in Table To apply DSCNet CLIP features, use MLPs with two hidden layers to replace the stacked convolutional encoder and decoder. As demonstrated in Sec. B.I we report the best clustering results after the tuning of papee-ppraaeters. As analyzed in (Haeffele al. 202T) and Section 2.1 DSCNet overly compresses the representations and yields unsatisfactory clustering results.
Out of domain datasets. We evaluate the capability to refine features by training PRO-DSC
with pre-trained CLIP features on out-of-domain datasets, namely, MNIST (Degg 2012). Fash-
ion MNIST (Xiao et al. 2017) and Oxford flowers (Nilsback & Zisserman 2008 As shown in Table B.3 CPP (Chu et al. 2024) refines the CLIP features and yields better clustering performance comparing with spectral clustering (Shi & Malik, 2000) and EnSC (You et al. 2016a). Our PRO- DSC further demonstrates the best performance on all benchmarks, validating its effectiveness in refining input features.
26

---

Published as a conference paper at ICLR 2025
Table B.4: Clustering accuracy CLIP features and learned representations. We apply k- means, spectral clustering, and EnSC to cluster the representations.
CIFAR-10
CIFAR- 1-0
CIFAR-20
TinylngNet-200
k-means
SC
EnSC
k-means
SC
EnSC
A-means
SC
EnSC
A-means
SC
EnSC
CLIP
74.7
70.2
95.4
52.8
66.4
67.0
46.9
49.2
60.8
54.1
62.8
64.5
SEDSC
16.4
18.9
16.9
5.4
4.9
5.3
11.7
10.6
12.8
5.7
3.9
7.2
CPP
71.3
70.3
95.6
75.3
75.0
77.5
55.5
43.6
58.3
62.1
58.0
67.0
PRO-DSC
93.4
92.1
95.5
76.5
75.2
77.6
66.0
59.7
60.0
67.6
67.0
69.5
Table B.5: Experiments on out-of-domain datasets.
MNIST
F-MNIST
Flowers
Methods
ACC
NMI
ACC
NMI
ACC
NMI
Spectral Clustering (Shi & Malik 2000
74.5
67.0
64.3
56.8
85.6
94.6
EnSC You et al. 2016a CPP (Chu el al. 2024
91.0
85.3
69.1
65.1
90.0
95.9
95.7
90.4
70.9
68.8
91.3
96.4
PRO-DSC
96.1
90.9
71.3
70.3
92.0
97.4
Experiments block diagonal regularizer with different k. To test the robustness of block diag- onal regularizer ||Al|j |ا to different k we vary & and report the clustering performance in Table B.6 As illustrated, & does not necessarily equal to the number of clusters. There exists an interval within which the regularizer works effectively.
Table B.6: Clustering performance with different k in block diagonal regularizer.
5
10
20
25
ACC
97.2
97.2
97.4
96.3
96.3
95.4
94.0
CIFAR-10
NMI
93.2
93.2
93.5
92.0
92.0
90.7
88.6
k
25
50
75
100
125
150
200
ACC
74.3
76.7
78.1
78.9
76.4
74.8
CIFAR-100
NMI
80.9
82.3
83.2
82.9
83.2
82.2
81.5
But if is significantly smaller than the number of clusters, the effect block diagonal regularizer will be subtle. Therefore, the performance of PRO-DSC will be similar to that of PRO-DSC without a regularizer (see ablation studies in Section 3}. contrary, if is significantly larger than the number of clusters, over-segmentation will occur the affinity matrix, which has negative impact on the subsequent clustering performance.
Clustering ImageNet-lk with DINO and MAE. To test the performance of PRO-DSC based on more pre-trained features other than CLIP [Radford et al.] 2021), we further conduct experiments on ImageNet- 1 (Deng al. 2009) pre-trained by DINO (Caron al. 2021 and MAE (He et al.)
2022] (see Table B.7).
DINO and MAE are pre-trained on ImageNet-Ik without leveraging external training data, thus their performance on PRO-DSC is lower than CLIP. Similar to the observations in CPP (Chu et al.) 2024). DINO initializes PRO-DSC well, yet MAE fails, which attributed to the fact that features from MAE prefer fine-tuning with labels, while they are less suitable for learning inter-cluster dis- criminative representations (Oquab et al. 2024). We further extract features from the validation set of ImageNet- and visualize through J-SNE (Van der Maaten & Hinton 2008) to validate the hypothesis (see Figure B.2).
B.3.4 EXPERIMENTS WITHOUT USING PRE-TRAINED MODELS
Experiments on Reuters and UCI HAR. During the rebuttal, we conducted extra experiments on datasets Reuters and UCI HAR. The dataset Reuters- 10k consists of four text classes, containing 10,000 samples of 2,000 dimension. The UCI HAR is time-series dataset, consisting of six classes, 10,299 samples of 561 dimension. We take EDESC (Cai et al. 2022 as the baseline method for
27

---

Published as a conference paper at ICLR 2025
Table B.7: Clustering Performance of PRO-DSC based on DINO and CLIP pre-trained features on ImageNet-Ik, lk.
PRO-DSC ACC
k-means
Method
Backbone
NMI
ACC
NMI
MAE
(He al.
2022
VIT L/16
9.0
49.1
9.4
49.3
DINO
2021
VIT B/16
57.3
79.3
52.2
79.2
DINO
Caron
2021
VIT B/8
59.7
80.8
54.6
80.5
CL.IP Radford et al.
2021
VIT 1/14
65.1
83.6
52.5
79.7
30-
-00
-00
100
-40
-30
100
-20
-50
-45
-25
20:
80
(a) CLIP
(b) MAE
Figure B.2: The t-SNE visualization of CLIP and MAE features on the validation set ImageNet- lk.
deep subspace clustering on Reuters- 10kk and take N2D (MeConvilee et al. 202T) and FCMI Zeng et al.) (2023) the baseline methods for UCI HAR. in which the results directly cited from the respective papers. We conducted experiments with PRO-DSC on Reuters and UCI HAR following the protocol for data processing the baseline methods. We train and test PRO-DSC the entire dataset and report the results over trials. Experimental results are provided in Table B.S The hyper-parameters used for PRO-DSC is listed in Table B.9
Table B.8: Experimental Results on Datasets Reuters and UCI HAR with 10 trials. The results of other methods are cited from the respective papers.
REUTERS-I00
UCI HAR
Dataset
ACC
NMI
ACC
NMI
k-means (MacQueen. 1967)
52.4
31.2
59,9
58.8
SC Shi & Malik 2000)
40.2
37.5
53.8
74.1
AE Bengro et al. 2006)
59.7
32.3
66.3
60.7
VAE Kingma & Welling 2014)
62.5
32.9
JULE Yang et al. 2016
62.6
40.5
DEC (Xe al. 2016
75.6
68.3
57.1
65.5
DSEC (Chang et al
2018
78.3
70.8
EDESC (Cai et 2022)
82.5
61.1
DFDC (Zhang Davidson 2021
86.2
84.5
N2D McConville et al. 2021
82.8
71.7
FCMI Zeng et al. 2023
88.2
80.7
PRO-DSC
85.7 + 1.3
64.6 + 1.3
87.1 + 0.4
80.9 + 1.2
28

---

Published as a conference paper at ICLR 2025
Table B.9: Configuration of hyper-parameters for experiments on Reuters, UCI HAR, EYale-B, ORL and COIL-100.
Dataset
17
dpre
d
#epochs
#warm-up
Y
REUTERS-I0E
10
1024
128
100
1024
50
50
200
UCI HAR
10-4
1024
128
100
2048
20
100
300
EYale-B
10-4
1080
256
10000
2432
100
200
50
ORL
10
80
64
5000
400
100
75
10
COIL-100
10-4 12800
100
10000
7200
100
200
100
Comparison to AGCSC and SAGSC on Extended Yale B, ORL, and COIL.-10,, During the re- buttal, we conducted more experiments two tfate-of-the-art subspace clustering methods AGCSC eWei al. (023) and ARSSC (Wang et al. 2023a). Since that both of the two methods cannot handle the datasets used for evaluating
conducted experiments the datasets: Extended Yale B (EYaleB), ORL, and COIL-100 100. We set the architecture of pre-feature layer in PRO-DSC as the same the encoder of DSCNet (Ji al. 2017). The peeer-parameters configuration for training PRO-DSC is summarized in Table B.y We repeated experiments for 10 trails and report the aver- age with standard deviation in B.ble|B.10 As baseline methods, we use EnSC (You et al. 201 6a), SSCOMP YYou et al., 2016b). S (Chen et al. 2020b), DSCNet, DSSC (Lim et al. 2020) and DELVE Zhao al. (2024). The results of these methods, except for S*COMP and DELVE, E, are directly cited them from DSSC (Lim al. 2020), and the results of C*CMMP and DELVE are cited
PRO-DSC,
from their own papers.
Comparison to AGCSC. Our method surpasses AGCSC the Extended Yale B dataset and achieves comparable results on the ORL dataset. However, AGCSC cannot yield the result on COIL-100 24 hours.
Comparison to ARSSC. ARSSC employs three different non-convex regularizers: E, norm Penalty (I.P), Log-Sum Penalty (LSP)), and Minimax Concave Penalty (MCP). While ARSSC-MCP performs the best Extended Yale B, our PRO-DSC outperforms ARSSC- MCP on ORL. While AGCSC performs the best on ORL, but it yields inferior results on Extended Yale B and it cannot yield the results COIL-100 in 24 hours. Thus, did not report the results of AGCSC on COIL-100 and marked as Out of Time (OOT). Our PRO-DSC performs the second best results Extended Yale B, ORL and the best results on COIL-100. Since that we have not found the open-source code for ARSSC, we are un- able have their results COIL-100. This comparison also confirms the scalablity of PRO-DSC which is due to the re- parametrization (similar to SENet).
Table 1.10: Experiments on Extended Yale B, ORL and COIL-100.
BYale-B
ORL
COIL-100
ACC
NMI
ACC
NMI
ACC
NMI
EnSC
65.2
73.4
77.4
90.3
68.0
90.1
SSCOMP
78.0
84.4
66.4
83.2
31.3
58.8
CCOMP-CC
Chen et
2020b
87.4
78.9
DSCNet
69.1
74.6
75.8
87.8
49.3
75.2
DELVE
Zhao al
2024
89.8
90.1
79.0
93.9
JDSSCC
Li et al. 2020
92.4
95.2
78.5
90.6
79.6
94.3
A-DSSC
Lim al
2020
91.7
94.7
91.0
82.4
94.6
AGCSC
Wei et al.
92.3
94.0
92.8
OOT
OOT
ARSSC-
Wang el al.
95.7
75.5
ARSSC-LSP
Wang
20254
95.9
71.3
ARSSC-MCT
(Wang et all
20258
99.3
72.0
PRO-DSC
96.0 d: 0.3
95.7 0.8
83.2 -:: 2.2
92.7 = 0.6
82.8 4: 0.9
95.0 0.6
B.4 MORE VISUALIZATION RESULTS
Gram matrices and PCA visualizations. To qualitatively validate that PRO-DSC learns represen- tations aligning with union--o--orrhhgooas-sugggeeee distribution, visualize the Gram matrices
29

---

Published as a conference paper at ICLR 2025
and PCA dimension reduction results of CLIP features and learned representations from PRO-DSC for each dataset. As shown in Figure B.3 the off-block diagonal values decrease significantly, im- plying the orthogonality between representations from different classes. The orthogonal between subspaces can also he observed from the PCA dimension reduction results.
Singular values visualization. To show the intrinsic dimension of CLIP features and the represen- tations of PRO-DSC, We plot the singular values of CLIP features and PRO-DSC's representations in Figure B.4 Specifically, the singular values of features from all the samples are illustrated on the left and the singular values of features within each class are illustrated on the middle and right. As can be seen, the singular values of PRO-DSC decrease much slower than that of CLIP, implying that the features of PRO-DSC enjoy a higher intrinsic dimension and more isotropic structure in the ambient space.
Learning curves. We plot the learning curves with respect to loss values and performance of PRO- DSC on CIFAR-100, 100, CIFAR-20 and ImageNet-1k 1k in Figure B.5a Figure [B.5 and Figure B.5c respectively. Recall that L1 == -3 = log det (I + az Ze). L2 = Ze ZeCo | and L3 = Since L1 is the only loss function used in the warm-up stage, we plot all the curves
|| |z.. starting from the iteration when warm-up ends. As illustrated, the clustering performance of PRO- DSC steadily increase as the loss values gradually decrease, which shows the effectiveness of the proposed loss functions in PRO-DSC.
I-SNE visualization of learned representations. We visualize the CLIP features and cluster repre- sentations learned by PRO-DSC leveraging t-SNE (Van der Maaten & Hinton, 2008) in Figure B.6 As illustrated, the learned cluster representations are significantly more compact compared with the CLIP features, which contributes to the improved clustering performance.
Subspace visualization. We visualize the principal components of subspaces learned by PRO-DSC in Figure [.7] For each cluster in the dataset, we apply Principal Component Analysis (PCA) to the learned representations. We select the top eight principal components to represent the learned subspaces. Then, for each principal component, we display eight images whose representations are most closely aligned with that principal component.
Interestingly, we can observe specific semantic meanings from the principal components learned by PRO-DSC. For instance, the third row of Figure B.7a consists of stealth fighters, whereas the fifth row shows airliners. The second row of Figure B. 7c consists of birds standing and resting, while the sixth row shows flying eagles. While Figure B. consists of all kinds of trucks, the first row shows fire trucks.
C LIMITATIONS AND FAILURE CASES
In this paper, we explore an effective framework for deep subspace clustering with theoretical justification. However, it is not clear how to develop the geometric guarantee for our PRO-DSC framework to yield correctly peispacc-preserving solution. Moreover, it is unsuper- vised learning framework, we left the extension to semi-supervised setting as future work.
Limitations:
Failure Cases: In this paper, we evaluate our PRO-DSC framework on four scenarios of synthetic data (Fig. 5 B.I.. six benchmark datasets with CLIP features (Table five benchmark datasets with BYOL pre-trained features (Table B.3 three out-of-domain datasets (Table [.5)). using four different regularization terms (Table 3) using different feature extractor (Table B.7) and varying syper-parameters (Fig. and Table B.6). We also conduct experiments on two face image datasets
(Table [O).). text and temporal dataset (Table However, as demonstrated in Fig. [ our PRO- DSC will fail the sufficient condition to prevent catastrophic collapse is not satisfied by using improper hyper-parameters y and a.
Extensibility: As general framework for self-expressive model based deep subspace clustering, our PRO-DSC is reasonable, scalable and flexible to miscellaneous extensions. For example, rather than using log (.t(.), there are other methods to solve the feature collapse issue, e.g., the nuclear norm. In addition, it is also worthwhile to incorporate the supervision information from the pseudo- al. 2017), for further improving the performance
label, e.g., (Huang et al. 2023 Jia et al. 2025 of our PRO-DSC.
30

---

Published as a conference paper at ICLR 2025
Aguatc
Aquadi
Pahh
(a) CIFAR-20
200
100
200
Agglt
AQUAFME
D2Y
Apple
Aquetan
Baby
(b) CIFAR- 100
Salvrwwder
(c) TinylmageNet-2000
200
Tay
(d) ImageNet-Dogs-I.
300 000 ABC MECDROIIN
(e) ImageNet-
Figure B.3: Visualization of the union-of-orrtogonalssubbeee sentations via Gram matrix and PCA dimension reduction on three categories. Left: X x Mid-left: Z Z Mid-right: X(3) via PCA. Right: Z(a) via PCA.
structure of the learned repre-
31

---

Published as a conference paper at ICLR 2025
Skypber vdao of mag3o
Stapdar JCUUP ca cba
Stagdar vakeo 1EP00-00 from cadi der
1.5
1.0
1.0
Notratie Vatoo
CLIP
Nocellad
E4
022
0.2
0:0
20
10
Ouspasats
Compences
(a) CIFAR-100
Skyyder vaaa of miaplzzo
Standaarvaoo aECLUP bra cla
Stagdar PEROO-SS from
CLP
PRO-USC
0.8
NocteBaed Vilee
D.5-
3.6
0.4
Compasiox
Componente
Campaners
(b) Tin-1mageNet-200
Noreattrd Nitoo
Caso
CLIP PRO-D6C
0.4
0
30
10
Componints
(c) ImageNet-
Figure B.4: Singular values of features from all samples (left) and features from each class (mid and right). For the better clarity, we plot the singular values for the first ten classes.
32

---

Published as a conference paper at ICLR 2025
100
0.3
1.2
88
0.2
ACC
9.6
-200
330
Epochs
(a) CIFAR 20
-1.0
-142
0.6
FLU
ACC XMI
0L3
LLB
-109
-148
0.2
0.4
-1.0
200
1300
1400
2000
2000
3200
200
(80)
1901
2000
2600
ION0
200
800
1400
2000
2500
3200
10
28
30
40
50 60
80 50 100
Egeche
(b) CIFAR-100
-1000
-1840
11800
30
ACC
-3960
0,5
40
-2500
30
2000
22000
42000
$2000
2000
22000
43001)
63000
50
75
101
Pteratioos
Beratioos
Berratioss
Epochs
(c) ImageNet- 1k
Figure B.5: The learning w.r.t. loss values and evaluation performance of PRO-DSC CIFAR-20, CIFAR-100 and ImageNet-1k lk dataset.
60
-20
-00
(a) CLIP CIFAR-10
(b) PRO-DSC CIFAR- 10
72-
54-
20
25
-30
-20
CLIP CIFAR-100
(d) PRO-DSC CIFAR-100
Figure B.6: t-SNE visualization of CLIP features and PRO-DSC's learned representations. The experiments are conducted on CIFAR-10 and CIFAR-100 dataset.
33

---

Published as a conference paper at ICLR 2025
(a) Cluster
(b) Cluster 2
Cluster
(d) Cluster
(c) Cluster 5
Cluster
(g) Cluster
(h) Cluster 8
(i) Cluster
(j) Cluster 10
Figure B.7: Visualization of the principal components in CIFAR-10 dataset. For each cluster, we display the most similar images to its principal components.
34


Reviews:
[{"review_id": "3IjUZeenPK", "reviewer": "Reviewer_KBNV", "summary": "The paper studied deep subspace clustering. Existing deep subspace clustering methods suffer from feature collapse, where learned representations collapse into subspaces with dimensions much lower than the ambient space. The paper proposes to add a loss term that alleviates this issue, which is backed up with some theoretical study and experiments on real-world dataset.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Experiments on synthetic and real-world datasets are comprehensive, and the reviewer appreciate that.  Synthetic experiments: what happens when you add an additional subspace? Case 1: the subspace is 0-dimensional (points centered around a centroid) Case 2: you add a another curve as you have around the great circle, but now put it vertically. The subspaces will be intersecting. I am not expecting the methods to outperform anything, this is just for understanding the method better.", "weaknesses": "1. The reviewer is concerned with the novelty of the paper. The main motivation of the paper is the observation from Haeffele el al. 2021 that if one learns a representation and apply a subspace clustering type of loss on the representations, then the representations tend to collapse. Therefore, the paper proposes to incorporate an additional term (equation 3) into the loss to prevent collapse. This theme of combining subspace clustering loss and (equation 3) has been explored before: In Ding et al 2023, they used a combination of (equation 3) and the subspace clustering loss in Ma et al 2007. One could go ahead and try many different subspace clustering loss functions, but the contribution seems incremental apriori. If one reads the introduction of that paper, it appears that the motivation was rather similar to this one, but no discussion was given in the current paper.\n2. The reviewer is also concerned with the theoretical contributions. \n    1. Lemma 1 and its proof is not a contribution, as the paper clearly states they are from Haeffele et al. 2021.\n    2. It is difficult to connect Theorem 1 with the main objective (equation 5). In particular, it is unclear at the optimality of (equation 5), whether (and why) the optimal Lagrangian multiplier nu satisfies the conditions in Theorem 1.\n    3. Theorem 3: I do not quite understand the statement. \n        1. First, apriori there might be multiple solutions to PRO-DSC. When you say ‘the’ optimal solution, what do you mean? Do you mean you have a sufficient condition, such that there exists ‘one’ optimal solution such that some ideal properties hold on this solution? Or do you mean ‘all’ optimal solutions\n        2. Second, I am a bit confused on Z, C vs Z^*, C^*. Gamma is defined to permute (or ‘align’) columns of Z, but on line 238 they are used to permute Z^*. Is Gamma a function of Z or Z^*? In the sufficient condition &lt;(I-C)(I-C)^T, G-G^*>, should it be C^* instead? Or even a step back: how is C defined in Theorem 3?\n        3. It is unclear what how to interpret sufficient condition &lt;(I-C)(I-C)^T, G-G^*>, e.g., how does it connect with Z^* lying in a union of subspaces or C^* being correctly connecting points only from the same subspace. It might strengthen the result a bit if there is a simple case (e.g., the subspaces are independent or orthogonal, points being uniformly spread within each subspace) where such conditions hold. \n\nI am in general happy to adjust my ratings based on whether the rebuttal addresses the comments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "I70A5HavAr", "reviewer": "Reviewer_eucv", "summary": "This paper proposed a Principled fRamewOrk for Deep Subspace Clustering (PRO-DSC), which is designed to learn structured representations and self-expressive coefficients in a unified manner. First, PRO-DSC incorporates an effective regularization into self-expressive model to prevent the catastrophic representation collapse with theoretical justification. Second, PRO-DSC demonstrated that it is able to learn structured representations that form a desirable UoS structure, and also developed an efficient implementation based on reparameterization and differential programming. Comprehensive experiments verify the superiority of the proposed model.", "questions": "1.What are the limitations and failed cases of the proposed method? Some discussion needed.\nThere may be insufficient implementation details provided, hindering reproducibility of the study and making it challenging for other researchers to replicate the results. Such as, the results for PRO-DSC are averaged over three trials (with±std), what about other methods? Their results are the best or mean? As I know, some methods like k-means and SC are sensitive to the initialization, their results are recorded by the best or mean in some runs with different initializations? A fair experimental setting is necessary.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The paper is well-written and technically sound.  \n2.The experiments are comprehensive.", "weaknesses": "1.What are the limitations and failed cases of the proposed method? Some discussion needed.\n2.There may be insufficient implementation details provided, hindering reproducibility of the study and making it challenging for other researchers to replicate the results. Such as, the results for PRO-DSC are averaged over three trials (with±std), what about other methods? Their results are the best or mean? As I know, some methods like k-means and SC are sensitive to the initialization, their results are recorded by the best or mean in some runs with different initializations? A fair experimental setting is necessary.  \n3.The subspace description coefficients and manifold parts provided in the article are based on existing research results and lack sufficient innovation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "I0Dvw2a1gN", "reviewer": "Reviewer_6RSz", "summary": "This paper studies the deep subspace clustering problem. The general framework of the existing algorithms suffers from feature collapse and lacks a theoretical guarantee to learn the desired UoS representation. This paper presents a principled framework for deep subspace clustering (PRO-DSC), which is designed to learn structured representations and self-expressive coefficients in a unified manner. The motivation is clear, and the experimental performance of the proposed model is also good.", "questions": "See the weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe motivation is clear.\n2.\tThe proposed method has strong theoretical support. \n3.\tThe problem that needs to be solved is important, and the proposed method is reasonable.", "weaknesses": "In Eq. (4), it needs to be clarified why the logdet term is adopted. Is it only used to solve the representation collapse problem? Are there any other methods that can solve this collapse problem? More importantly, what are the underlying physical meanings of this term?\n\nIn Table 2, although the proposed methods seem to have the best performance. Some really SOTA deep clustering methods are not compared, like \n[1] Learning Representation for Clustering Via Prototype Scattering and Positive Sampling, 2023 TPAMI.\n[2] Towards Calibrated Deep Clustering Network, 2024 Arxiv.\n\nAblation studies should be performed to check the effectiveness of each component of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "hKkUiYRNab", "reviewer": "Reviewer_JbyQ", "summary": "Deep subspace clustering methods usually encounter the challenge of feature collapse and lack theoretical guarantees for learning representations that form a union of subspaces (UoS) structure. To address these issues, this paper presents a principled framework for deep subspace clustering (PRO-DSC). The framework incorporates an effective regularization on the learned representations to prevent feature space collapse. Furthermore, theoretical analysis demonstrates that PRO-DSC can yield representations of a UoS structure under certain conditions. Experimental results show the effectiveness of the proposed method.", "questions": "I have several questions and concerns regarding the experimental parts:\n1) Why is only the proposed method run multiple times for evaluation, while other methods seem to be tested only once? Additionally, why is the method run only three times? Repeating the evaluation 10 times is commonly preferred for more reliable results.\n2) Why are only image datasets used for evaluation? I suggest testing the performance on a wider range of datasets, such as the Reuters and UCI HAR datasets.\n3) Most of the comparison methods used in experiments are outdated. Please consider adding two more state-of-the-art subspace clustering methods for comparison, such as AGCSC [1] and SAGSC [2].\n4) Why do the comparison methods differ between experiments in Tables 1 and 2?\n5) In the synthetic data experiments, why is DSCNet used as the representative SEDSC method rather than the more competitive, recent SENET?\n\n[1] Wei, Lai, et al. \"Adaptive graph convolutional subspace clustering.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.\n\n[2] Wang, Libin, et al. \"Attention reweighted sparse subspace clustering.\" Pattern Recognition, 139 (2023): 109438.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work presents an effective method to prevent feature collapse and addresses the lack of theoretical guidance for learning representations with a UoS structure. An efficient implementation is presented to alleviate the computational burden of self-expressive learning.\n2. The work is sound from a technical perspective. It combines solid theoretical proof and empirical evidence. \n3. Experiments on synthetic and real-world data are conducted to evaluate the effectiveness. Meanwhile, both quantitative and qualitative results are provided for comparison.\n4. Overall, this paper is well-written and thoughtfully structured.", "weaknesses": "1. As one of the main challenges this work focuses on is learning UoS representations, I suggest the authors emphasize the significance of this challenge by clarifying the associated consequences and providing empirical observations to support it.\n2. Since the proposed PRO-DSC is designed as a framework, I expect further discussion and experimentation on its scalability and extensibility.\n3. I have several questions and concerns regarding the experimental parts:\n    1) Why is only the proposed method run multiple times for evaluation, while other methods seem to be tested only once? Additionally, why is the method run only three times? Repeating the evaluation 10 times is commonly preferred for more reliable results.\n    2) Why are only image datasets used for evaluation? I suggest testing the performance on a wider range of datasets, such as the Reuters and UCI HAR datasets.\n    3) Most of the comparison methods used in experiments are outdated. Please consider adding two more state-of-the-art subspace clustering methods for comparison, such as AGCSC [1] and SAGSC [2].\n    4) Why do the comparison methods differ between experiments in Tables 1 and 2?\n    5) In the synthetic data experiments, why is DSCNet used as the representative SEDSC method rather than the more competitive, recent SENET?\n\n[1] Wei, Lai, et al. \"Adaptive graph convolutional subspace clustering.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.\n\n[2] Wang, Libin, et al. \"Attention reweighted sparse subspace clustering.\" Pattern Recognition, 139 (2023): 109438.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)