A Critique of Self-Expressive Deep Subspace Clustering
Authors: Benjamin David Haeffele
Chong You
Rene Vidal
Venue: ICLR 2021 Poster (2021)
Keywords: Subspace clustering
Manifold clustering
Theory of deep learning
Autoencoders

Abstract: Subspace clustering is an unsupervised clustering technique designed to cluster data that is supported on a union of linear subspaces, with each subspace defining a cluster with dimension lower than the ambient space. Many existing formulations for this problem are based on exploiting the self-expressive property of linear subspaces, where any point within a subspace can be represented as linear combination of other points within the subspace. To extend this approach to data supported on a union of non-linear manifolds, numerous studies have proposed learning an embedding of the original data using  a neural network which is regularized by a self-expressive loss function on the data in the embedded space to encourage a union of linear subspaces prior on the data in the embedded space. Here we show that there are a number of potential flaws with this approach which have not been adequately addressed in prior work. In particular, we show the model formulation is often ill-posed in that it can lead to a degenerate embedding of the data, which need not correspond to a union of subspaces at all and is poorly suited for clustering. We validate our theoretical results experimentally and also repeat prior experiments reported in the literature, where we conclude that a significant portion of the previously claimed performance benefits can be attributed to an ad-hoc post processing step rather than the deep subspace clustering model.

Published as a conference paper at ICLR 2021
A CRITIQUE OF SELF-EXPRESSIVE DEEP SUBSPACE CLUSTERING
Benjamin D. Haeffele
Chong You
Mathematical Institute for Data Science Johns Hopkins University
Department of Electrical Engineering and Computer Sciences University of California, Berkeley Berkeley, CA, USA cyoubberkeley.cm
Baltimore, MD, USA bhaeffele@ jhu edu
René Vidal
Department of Biomedical Engineering Johns Hopkins University Baltimore, MD, USA
ABSTRACT
Subspace clustering is unsupervised clustering technique designed to cluster data that is supported on a union of linear subspaces, with each subspace defining cluster with dimension lower than the ambient space. Many existing formu- lations for this problem are based on exploiting the self-cxpressive property of linear subspaces, where any point within subspace can be represented as linear combination of other points within the subspace. To extend this approach to data supported on a union of non- non-linear manifolds, numerous studies have proposed learning an embedding of the original data using neural network which is reg- ularized by self-expressive loss function on the data the embedded space to encourage a union of linear subspaces prior on the data in the embedded space. Here we show that there are number of potential flaws with this approach which have not been adequately addressed in prior work. In particular, we show the model formulation is often ill- ill-posed that it can lead to a degenerate embedding of the data, which need not correspond suited for clustering. We validate our theoretical results experimentally and also repeat prior experiments reported in the literature, where conclude that sig- nificant portion of the previously claimed performance benefits can be attributed an ad-hoe post processing step rather than the deep subspace clustering model.
union of subspaces at all and is poorly
INTRODUCTION AND BACKGROUND
Subspace clustering is a classical unsupervised learning problem, where one wishes to segment a given dataset into a prescribed number of clusters, and each cluster is defined as a linear (or affine) subspace with dimension lower than the ambient space. There have been a wide variety of approaches proposed the literature to solve this problem (Vidal et al., 2016). but a large family of Hlate-of-the oftt---rr--- approaches
based exploiting the self-expressive property of linear subspaces. That is, if a point lies in a linear subspace, then it can be represented as a linear combination of other points within the subspace, Based on this fact, wide variety of methods have been proposed which, given a dataset E d of N d-dimensional points, find matrix of coefficients C E N by solving the problem:
F(Z, C) 1 2|2 +O(C) = 1 Z. (D-(CC-)) { (1) min CERNXN
Here, the first term IC C captures the self-expressive property by requiring every data- point represent itself as approximate linear combination of other points, i.c., Z, ZC, where Z, and C, are the th columns of and C, respectively. The second term, (CC), is some regularization function designed encourage each data point to only select other points within the

---

Published as a conference paper at ICLR 2021
correct subspace in its representation and to avoid trivial solutions (such as C = I). Once the C matrix has been solved for, one can then define a graph affinity between data points, typically based on the magnitudes of the entries of C, and use appropriate graph-baset based clustering method (e.g.,
spectral clustering (von Luxburg 2007 to produce the final clustering of the data points.
One of the first methods to utilize this approach was Sparse Subspace Clustering (SSC) (Elhamifar & Vidal 2009 2013), where 9 takes the form (C) = ||C||| + ((diag(C) = -), with denoting the norm and 0 an indicator function which takes value do if an element of the diagonal of C is non-zero and 0 otherwise. By regularizing C to be sparse, a point must represent itself using the smallest number of other points within the dataset, which in turn ideally requires a point to only select other points within its own subspace in the representation. Likewise other variants, with Low-Rank Representation (LRR) (Liu et al., 2013), Low-Rank Subspace Clustering (LRSC) (Viaal & Favaro 2014) and Elastic-net Subspace Clustering (EnSC) (You et al.) 2016) being well- known examples, take the same form as (T) with different choices of regularization. For example, (CR = ClI and (C) = ||C]| + 7 C| + (Cdiag(C) = 0), where || ||+ denotes the nuclear norm (sum of the singular values). A significant advantage of the majority of these methods is that it can be proven (typically subject to some technical assumptions regarding the angles between the underlying subspaces and the distribution of the sampled data points within the subspaces) that the optimal C matrix in ④ will be "correct" in the sense that if C.,; is non-zero
then the 1th and jth columns of Z lie in the same linear subspace (Soltanolkotabi & Candès 2012 Lu
eet al. 2012, Elhamifar & Vidal, 2013]] [So Soltanolkotabi et al., (0144] Wang et al.] [2015] Wang & Xu
2016
You & Vidal| 2015a bj Yang et al.) [2066] Tsakiris & Vidal 2018 Li et al.] [018]] You et al.,
2019 Robinson et al. 2019)), which has led to these methods achieving state-of- -hte-offthheart performance
in many applications.
1.1 SELE-EXPRESSIVE DEEP SUBSPACE CLUSTERING
Although subspace clustering techniques based self-expression display strong empirical perfor- mance and provide theoretical guarantees, a significant limitation of these techniques is the require- ment that the underlying dataset needs to be approximately supported on a union of linear subspaces. This has led to a strong motivation to extend these techniques to more general datasets, such as data supported on a union of non- non-linear diwdeeinniinal manifolds. From inspection of the right side of (I). one can observe that the only dependence on the data Z comes in the form of the Gram matrix Z Z. As a result, self-expressive subspace clustering techniques are amendable to the "kernel- trick", where instead of taking an inner product kernel between data points, one can instead use general kernel -): (Patel & Vidal 2014). Of course, such an approach comes with the traditional challenge of how select appropriate kernel so that the embedding of the data in the Hilbert space associated with the choice of kernel results in a union of linear subspaces.
The first approach to propose learning appropriate embedding of an initial dataset X E Rd, x (which does not necessarily have a union of subspaces structure) was given by Patel et al.] (2013) 2015) who proposed first projecting the data into lower dimensional space via learned linear projector, Z = P,X, where P, E Raxddz (d < dz) is also optimized over in addition to C in (I. To ensure that sufficient information about the original data X is preserved in the low-dimensional em- bedding Z, the authors further required that the linear projector satisfy the constraint that P.P, = I and added an additional term to the objective with form |X - P. P/X However, since the pro- jector is linear, the approach is not well suited for nonlinear manifolds, unless it is augmented with a kernel embedding, which again requires choosing a suitable kernel.
More recently, given the success of deep neural networks. a large number of studies Peng et al. (2017); Ji et al. (2017); Zeng et al.] (2019b)a), Xie et al. (2020); Sunn et al.] (2019); Li et al. (2019); Yang et al. (2019) : Jiang et al. (219(201))) Tang et al. (018)); Kheirandishfard et al. (2020b) : Zhou et al. (201)) Diang et al. (2018); Abavisani& & Patel 2018); Zhou et al. (2018); Zhang et al. 2018 2019b a): Kheirandishfard et al. (2020a) have attempted to learn an appropriate embedding of the data (which ideally would have union of linear subspaces structure) via a neural network, (X, We). where We denotes the parameters of a network mapping defined by & dg. which takes a input. In an attempt to encourage the embedding of the data, & We), to have this union of subspaces structure, these approaches minimize a self-expressive loss term, with form given in (T). on the embedded data, and a large majority of these proposed techniques can be
dataset X E Rd,
2

---

Published as a conference paper at ICLR 2021
SEDSC
Original Geometry
Auto-Enree Euto-Enccder
Geometry
Actual Geometry
Faggnder
(batanelBaacc
Dedoder
Figure I: Illustration of our theoretical results. The goal of the SEDSC model is to train network (typically an auto-encoder) to map data from a union of non-linear manifolds (Left) to a union of linear subspaces (Center). However, we show that for many of the formulations that have been proposed in the literature the global optimum of the model will have degenerate geometry in the embedded space. For example, in the Dataset and Channel/Batch normalization schemes Theorem 2 shows that the globally optimal geometry will have all points clustered near the origin with the exception of two points, which will be copies of each other (to within sign-flip) (Right).
described by the general form:
min 7 F(Z C) gZz C) subject to Z = (Xx W..C
(2)
where g is some function designed to discourage trivial solutions (for example $ F Wa) = 0) and 7 > 0 is some hyper-parameter to balance the terms.
Several different choices of g have been proposed in the literature. The first is to place some form of normalization directly Z. For example, Peng et al. (017)) propose Instance Normaliza- tion regularization, g (Z, X, C) = Σ (Z. Z. 1)2, which attempts to constrain the norm of the embedded data points to be 1. Likewise, one could also consider Dataset Normalization schemes, which bound the norm of the entire embedded representation |Z|
T or Channel/Batch Nor- malization schemes, which bound the norm of a channel of the embedded representation (i.e., a row of Z). Z 2 2 T, Vi. We note that this is quite similar to the common Batch Norm operator (Toffe & Szegedy 2015) used in neural network training which attempts to constrain each row of Z to have zero mean and constant norm.
Another popular form of is to also train a decoding network 4 p- Wa) with parameters Wa to map the self-expressive representation, (X, W. back to the original data to ensure that sufficient information is preserved in the self-expressive representation to recover the original data. We will refer to this as Autoencoder Regularization. This idea is essentially a generalization the previously discussed work, which considered constrained linear encoder/decoder mappings (Patel et al. 2013, Patel& & Vidal 20144] Patel et al.) 2015), to non-linear autoencodering neural networks and was first proposed by the authors of Ji et al. (017). The problem takes the general form:
min 7 (F, + [(X, Φ (ZC, Wa)) subject to = + F: (X, Wo),
(3)
W.. C.
where the first term is the standard self-expressive subspace clustering loss applied to the embedded representation, and the second term is standard auto-encoder loss, with typically chosen to be the squared loss. Note that here both the encoding/decoding network and the optimal self-expression encoding, C, are trained jointly, and once problem (3) is solved one can use the recovered C matrix directly for clustering.
Using the general formulation in (2 and the popular specific case in (3. Self-Expressive Deep Sub- space Clustering (SEDSC) has been applied to a variety of applications, but there is relatively little that it known about it from theoretical standpoint. Initial formulations for SEDSC were guided by the intuition that if the dataset is drawn from a union of linear subspaces, then solving problem (T) known to induce desirable properties C for clustering. By extension one might assume that one also optimizes over the geometry of the learned embedding (Z) this objective might induce desirable geometry in the embedded space (e.g.. a union of linear subspaces). However, a vast ma- jority of the prior theoretical analysis for problems of the form in [] only considers the case where the data is held fixed and analyzes the properties of the optimal C matrix. Due to the well-knows mapping functions (and hence
fact that neural networks are capable of producing a network could produce many potential values for Z), the use of a model such as (33) is essen- tially using (T) as regularization function on Z to encourage union of subspaces geometry. To
3

---

Published as a conference paper at ICLR 2021
date, however, models such (2 have been guided largely by intuition and significant questions remain regarding what type of data geometry is encouraged by F(Z, C)) when one optimizes over both the encoding matrix, C, and the network producing the embedded data representation, Z.
1.2 PAPER CONTRIBUTIONS
Here we explore these questions via theoretical analysis where we show that the use of F(Z, C) as a regularization function when learning a kernel from the data in an attempt to promote beneficial data geometries in the embedded space, as is done in 2 is largely insufficient in the sense that the opti- mal data geometries are trivial and not conducive to successful clustering in most cases. Specifically, we first note a basic fact that the Autoencoder Regularization formulation in (3) is typically ill-posed for most commonly used networks if constraints are not placed on the magnitude of the embedded on the autoencoder weights/arcchitecuur or an explicit normalization of O F5 (X, W.), such as in the Instance/Batch//aattse Normalization schemes. Then, even assuming that the embedded representation has been suitably normalized, we show that the optimal embedded data geometry encouraged by FIZ, C) trivial in various ways, which will depend on how the data is normalized. We illustrate our theoretical predictions with ex- periments on both real and synthetic data. Further, we show experimentally that much of the claimed performance benefit of the SEDSC model reported in previous work can be attributed to an ad-hoc post-processing of the C matrix first proposed in in et al. (2017).
data, & g (X. We), either through regularization/constaintt
Notation. We will denote matrices with capital boldfaced letters, Z, vectors which are not rows/columns of larger matrix with lower-case boldfaced letters, 2, and sets with calligraphic letters, 2. The ,th row of a matrix will be denoted with a superscript, 2); the 7th column of matrix will be denoted with a subscript, Zú; the jith entry of a matrix will be denoted as Zi and the 7h entry of a vector will be denoted as z, We will denote the minimum singular value of a matrix Z as o min (Z), and we will denote the nuclear, Frobenius, lp. and Schatten-p norms] for a matrix/vector as || ||. 1. ||Z]] r [Z]] |/ppp p. and [Z]|s, respectively. 8(end) denotes an indicator function with value 0 if condition end is true and oo otherwise.
2 THEORETICAL ANALYSIS
2.1 BASIC SCALING ISSUES
We begin our analysis of the SEDSC model by considering the most popular formulation, which is to employ Autoencoder Regularization as in (3). Specifically, we note that without any regularization on the autoencoder network parameters (We, Wa) or any normalization placed the embedded representation, & (X Wo). the formulation in (3) is often ill-posed in the sense that the value of FX@x(X, We), C) can be made arbitrarily small without changing the value of the autoencoder loss by simply scaling-down the weights in the encoding network and scaling-up the weights in the decoding network the magnitude of the embedded representation. As we will see, a sufficient condition for this to be possible is when the non non- non-linearity in the final layer of the encoder positively-homogenenne homogeneous We further note that most commonly used non- non-linearities in neural networks are positively homogenous, with Rectified Linear Units (ReLUs), leaky ReLUs, and max-pooling being common examples. As result, most autoencoder architectures employed for SEDSC will require some form of regularization or normalization for the F term to have any impact on the geometry of the embedded representation (other than trivially becoming smaller in magnitude), though many proposed formulations do not take this issue into account.
way which doesn't 't change the output of the autoencoder but reduces
As basic example, consider fully connecconee Angle-hiddenn-aye layer networks for the encoder/decoder, T (X, We) = W?(W! and T (Z, (Z) = (3(W!Z) where (x)+ = max fax 0} denotes the Rectified Linear Unit (ReLU) non-linearity applied entry-wise. Then, note that because the ReLU function is positively homogeneous of degree I for any a > 0 one has & Pe(X ee,XaW) = (a As a result one can scale We by any a 0 and Wa by a without changing the output of
d???(W!
a (X, We) and similarly for $ &D-
Recall, the Schatten-p norm of a matrix C is defined as the f, norm, p 2 1, of the singular values of C. Recall, function fz) is hooooeenoooom of degree p if fax) o" f(x), Yo 2 0.
4

---

Published as a conference paper at ICLR 2021
+ We). Wa). but (X aWe)lle = a a (|((ggX We]l From this, taking a to be arbitrarily small the magnitude of the embedding can also be made arbitrarily small, so if 0 () in ( is something like norm (as is typically the case) the value of F F(Z, C) in ) can also be made arbitrarily small without changing the reconstruction loss of the autoencoder l. This implies one is simply training an autoencoder without any contribution from the F(Z, C) term (other than trying to reduce the magnitude of the embedded representation). This basic idea can be easily generalized and formalized in the following statement (all proofs are provided in the Supplementary Material):
the autoencoder, dD( aW)),
Proposition Consider the objective in (3) and suppose (CC) in ①I is a function which achieves its minimum at C = 0 and satisfies ((CC) < ((C), Vu E (0.1). ffr any choice of (Wa, We) and T2 E (0, 1) there exists (Wa, We) such that (X, W.) (Z Wa) then the F term in (3) can be made arbitrarily small without changing the value of the loss function f. Further, if the final layer of the encoding network is costively-homoogen
(X, We) and ( Wa)
with degree p # O, such (Wa, We) will always exist simply by sealing the network weights of the linear (or affine) operator parameters.
In practice, most of the previously cited studies employing the SEDSC model use networks which satisfy the conditions of Proposition [ without regularization, and we note that such models can never be solved to global optimality (only approach it asymptotically) and are inherently ill-posed. From this, one can conclude that Autoencoder Regularization by itself is often insufficient to prevent trival solutions 2 This specific issue can be easily fixed (although prior work often does not) if one ensures that the magnitude of the embedded representation is constrained to be larger than some minimum value either through regularizztionn/onsttaant placed on the network weights, such as using weight decay or coupling weights between the encoder and decoder, potentially different choice of non- non-liie on the last layer or the encoder, or explicit normalization of the embedded representation. However, the question remains what geometries are promoted by |I even if the basic issue described above is corrected, which we explore next.
2.2 THE EFFECT OF THE AUTOENCODER LOSS
Before presenting the remainder of our formal results, we first pause discuss the effect of the autoencoder loss (f) in (3). The use of the autoencoder loss is designed to ensure that the embed- ded representation Z retains sufficient information about the original data X so that the data can be reconstructed by the decoder, but we note that this does not necessarily impose significant con- straints on the geometric arrangement of the embedded points in Z. While there is potentially some constraint on the possible geometries of Z which is imposed by the choice of encoder/decoder ar- chitectures, reasonably expressive encoders and decoders can map a finite number of data points arbitrarily into the embedded space and still decode them accurately, provided the embedding of any two points is still distinct to within some perturbation (i.e., & F is a one-to-one mapping on the points in X). Further, because we only evaluate the mapping on finite set of points X, this is a much easier (and can be achieved with much simpler networks) than the approximation regime of neural networks (which requires good approximation over the entire con- tinuous data domain), and it is well documented that typical network architectures can optimally fit fairly arbitrary finite training data (Zhang et al. 2017).
universal
Given the above discussion, in our analysis we will first focus on the setting where the autoencoder is highly expressive. In this regime, the encoder can select weight parameters to produce an essentially arbitrary choice of Z embedding, and as long as (Xx) # & &x{(X) vX; of X, then the decoder can exactly recover the original data X. As a result, for almost any choice of encoder the autoen- coder loss term, f, in (3) can be exactly minimized, so the optimal network weights for the model in (3) (and likewise (2) will be those which minimize F(Z, C) (potentially to within some small e perturbation so that & &x((' is one-to-one mapping on the points in X). As we already know from Prop [ this is poo-p without some additional form of regularization, so in the following subsec- tions we explore optimal solutions to F(Z, C) when one optimizes over both C and the embedded representation Z- = & g (X, We) subject to three different constraints on Z: (1) Dataset Normaliza- tion | 2 T. (2) Channel/Batch Normalization | 2 Vi, and (3) Instance Normalization |Z F = T Vi. Finally, after characterizing solutions to F(Z, C). we give a specific example of a
very simple (i.e., not highly expressive) family of architectures which can achieve these solutions,
5

---

Published as a conference paper at ICLR 2021
showing that the assumption of highly expressive networks is not necessary for these solutions to be globally optimal.
2.3 DATASET AND BATCH/CHANNER NORMALIZATION
We will first consider the Dataset and Batch/Channel Normalization schemes, which will both result in very similar optimal solutions for the embedded data geometry. Recall, that this considers when the entire dataset is constrained to have norm greater than some minimum value in the embedded space (Dataset Normalization) or when the norms of the rows of the dataset are constrained to have norm greater than some minimum value (Batch/Chhanel Normalization). We note that the latter case is very closely related to batch normalization [Toffe~ & Szegedy] 2015), which requires that each channcl/feature (in this case row of the embedded representation) have zero mean and constant norm in expectation over the draw of mini-batch. Additionally, while we do not explicitly enforce zero arrommean constraint, we will see that optimal solutions will exist which have zero mean. Now, if one optimizes FZZ, C) jointly over (Z, C) subject to the above constraint(s) on Z, then the following holds:
Theorem 1. Consider the following optimization problems which jointly optimize over Z and C:
(P1)
min (Z. s.t. |Z|| 2T (P2) min {F(Z. C) s.t. I 1 2 3 (4)
vi}
C.Z
C,
Then optimal values for C for both (P1) and (P2) are given by C' E arg min ii (C-II++++
(5)
C
Moreover, for any optimal C², let be the multiplicity of the smallest singular value of C* and let Q E x be an orthonormal basis for the subspace spanned by the left singular vectors
associated with the smallest singular value of C Then we have that optimal values for Z are given by:
[B B ]
miin ( (C* -) > 0
(P1)
[B B F 2 r}
muin (C* I) = =0
Z" E (BQ Be Raxr nB), B
(6)
[B B' || 5. Vi}
Mmin (C' 1) >
(P2)
(B:
B N d Vi} mmin (C* I)) 0
I)
From the above result, one notes from 5 that optimizing F(Z, C) jointly over both and C is
equivalent to finding C which minimizes trade-off between the minimum singular value of C --I and the regularization (CC). Further, we note that if such an optimal C results in the minimum singular value of C I having multiplicity of 1, then this implies that every data point in Z will simply be a scaled version of the same point. Obviously, such an embedding is not useful for subspace clustering. Characterizing optimal solutions (5) is somewhat complicated in the general case due to the fact that the smallest singular value is concave function of a matrix and 0 is typically chosen be a convex regularization function, resulting in the minimization of convex+concave function. Instead, we will focus on the most commonly used choices of regularization, starting with Assc C) ||C|| + 5(diag( C) 0), where we derive the optimal solution in the case where Tmin C I) 0. We note that this corresponds to the case where z Z C* which one typically obtains as X in [ taken be small.
Theorem 2. Optimal solutions to the problems
(P1) min Cll, s.t. diag(C) = 0, ZC,
|
2.C
(P2) min || s.t. diag(C) = 0, zc,
|
Vi
(8)
2.C
are characterized by the set
0 1
0
1 0
0
(Z", {|z
0dxN-2)PP x PT
0 0
0
P
(9)
where E N is an arbitrary gegned-permutatoon matrix and z E Rd is an arbitrary vector which satisfies | 2 7/2 for (P1) and xi 72d)), Vi E [1, d) for (P2).

---

Published as a conference paper at ICLR 2021
From the above result, we have shown that if Z is normalized to have a lower-bounded norm on either the entire embedded representation or for each row, then the effect of the F(Z, C) loss will be largely similar to the situation described by Proposition in the sense that the loss will still attempt to push all of the points to 0 with the exception of two points, which will be copies of each other (potentially within sign-flip). Again, the optimal embedded representation is clearly ill ill-posed for clustering since all but two of the points are trivially driven towards O in the embedded space.
In addition, we also present a result similar Theorem 2 when C is regularized by any Schatten-p norm, which includes two other popular choices of regularization that have appeared in the literature the Frobenius norm (CC) = | (for p 2) and the nuclear norm @(C) ||C||| (for p = 1) as special cases.
Theorem 3. Optimal solutions to the problems
(P1) min |Cls, s.t. Z ZC, |2| 2
(10)
Z.
(P2) min
[lls, s.t. Z Zc, | 11 à Vi,
(11)
Z.
norm where ||C||s, is any Schalten-p norm on C, are characterized by the set
(Z", E {(2q ) x (qq)) q R 1/q/// = 1]
(12)
where z E Rd is an arbitrary vector which satisfies |z | 2 r for (P1) and 2 2 2, Vi (P2).
Again, note that this is obviously not good geometry for successful spectral clustering as all the points in the dataset are simply arranged on a single line and the optimal C is a rank-one matrix.
2.4 INSTANCE NORMALIZATION
To explicitly prevent the case where most of the points in the embedded space are trivially driven to 0 as in the prior two normalization schemes, another potential normalization strategy which has been proposed for ? is use Instance Normalization (Peng al.) 2017), where the l2 norm of each embedded data point is constrained to be equal to some constant. Here again we will see that this results in somewhat trivial data geometries. Specifically, we will again focus on the choice of the (ssc C) regularization function when we have exact equality, Z = ZC, for simplicity of presentation. From this we have the following result:
Theorem 4. Optimal solutions to the problem
min
||Cl|2 s.t. diag(C) = 0, -= =CC, ZZ = Vi Z.C
(13)
must have the property that for any column in Z", Z there exists another column. Z (i + j). such that Z = =s,z where $i E 1). Further, || || = 1 Vi and C. # 0 = Z; = ZZ,.
The above result is quite intuitive in the sense that because a given point cannot use itself in its representation (due to the (Cag(C) = 0 constraint), the next best thing is to have an exact copy of itself in another column. While this result is more conducive to successful clustering in the sense that points which are close in the embedded space are encouraged to 'merge" into a single point, there are still numerous pathological geometries that can result. Specifically, there is no constraint on the number of 'distinct' points in the representation (i.e., the number of vectors which are not copies of each other to within sign flip), other than it must be less than N/2. As a result, the optimal C matrix can also contain an arbitrary number (in the range [1,) of connected components in the affinity graph, resulting in somewhat arbitrary spectral clustering.
Example of Degenerate Geometry with Simple Networks. In section 2.2 we discussed how if the encoder/decoder are highly expressive then the optimal embedding will approach the solutions we give in our theoretical analysis. Here show that trivial embeddings can also occur with relatively simple encoders/decoders. Specifically, consider basic encoder/decoder architectures which consist of two affine mappings with a ReLU non-linearity (denoted as (-)+) on the hidden layer:
+ fx Wa)
x + bb)+ by pz Wa) W3(W3> 2z + bb)+ + by
(14)
where the linear operators (W matrices) can optionally be constrained (for example for convolution operations W could be required to be a Toeplitz matrix). Now if we have that the embedded dimen- sion d is equal to the data dimension d, we will say that linear operators can express identity on X
7

---

Published as a conference paper at ICLR 2021
0011:00
DRL
Accurs (N)
Accuracy (N)
Accuracy (8)
Raw Data pp?
60
30
Autoene only
Autoane pp)
40
Pull SEDSC
Pull SEDSC
100
125
150
175
75
300
125
150
375
200
100
125
150
175 200
Barwlion/10
Iteration
Iteration/to
Clustering accuracy results for YaleB (38 faces), COIL100, and ORL datasets with (Dashed Lines) and without (Solid Lines) the post-processing step on matrix proposed in Ji et al. (017). (Raw Data) Clustering on the raw data. (Autoene only) Clustering features from an autoencoder trained without the FZZ, C) term. (Full SEDSC) The full model in (3.
Figure 2:
if there exists parameters (W2, W such that w = X. Note that if the architectures in (14) are fully-connected this implies that for a general X the number of hidden units is greater than or equal to d dz (which can be even smaller if X is low-rank), while the linear operators are con- volutions, then we only need one convolutional channel (with the kernel being the delta function). Within this setting we have the following result:
Proposition Consider encoder and decoder networks with the form given in (14). Then, given any dataset X Bd N where the linear operators in both the encoder/decoder express identity on X and any T > O there exist network parameters (We, Wa) which satisfy the following:
1. Embedded points arbitrarily close: | [X, We) - & (X,. Wc)l ((iij)) and Ve > 0. Embedded points have norm arbitrarily close to ||| WF = Vi and Ve 0. Embedded points can decoded exactly: p (X; W.), Wa) = X,, Vi.
From the above simple example, not necessarily highly expressive) it is still possible to have solutions which are arbitrarily close to the global optimum described in Theorem in the sense that the points can be made to be arbitrarily close to each other in the embedded space with norm arbitrarily close to t (for any arbitrary choice of r), while still having perfect reconstruction of X.
see that even with very simple network architectures (i.e..
EXPERIMENTS
Here, present experiments both real and synthetic data that verify our theoretical predictions experimentally. We first evaluate the Autoencoder Regularization form given in (3) by repeating all of the experiments from Ji al. (2017). In the Supplementary Material we first show that the optimization problem never reaches stationary point due to the pathology described by Prop [ (see Figure 4 in Supplementary Material), and below we show that the improvement in performance reported in Ji et al. (2017) is largely attributable to an ad-hoc post-processing step. Then, we present experiments on a simple synthetic dataset to illustrate our theoretical results.
Repeating the Experiments of Ji et al. (017). First we use the code provided by the authors of al. 2017) to repeat all of their original clustering experiments on Extended Yale-B (38 faces), ORL, and COIL100 datasets. As baseline methods, we perform subspace clustering the raw data as well as subspace clustering on embedded features obtained by training the autoencoder network without the (ZZ, C) term (i.e., further details.
0 and C fixed I in See Supplementary Material for
In addition proposing the model in the authors of Ji 2017) also implement somewhat arbitrary post-put processicg the matrix recovered from the SEDSC model before the final spectral
Table 1: Clustering accuracy shown in Fig 2
To be consistent with Ji et al. (2017). we report the COIL100) ORL, respectively.
results at 1000/ 12//1/0//000 iterations for Yale B
With post processing
Without post processing
Raw Data
Autoenc only
Full SEDSC
Raw Data
Autoene only
Full SEDSC
YaleB
94.40%
97.12%
96.79%
68.71%
71.96%
59.09%
COIL100
66.47%
68.26%
64.96%
47.51%
44.84%
45.67%
ORL
78.12%
83.43%
84.10%
72.68%
73.73%
73.50%
8

---

Published as a conference paper at ICLR 2021
Original Data Domain
Embedded Data Domain
[C]
[C] - log color scale
AutoEncader
Se Express
04-
Dataset Norm
Original Data
-42
-0.4
Figure 3: Results for synthetic data using the dataset normalization scheme. (Left) Original data points (Blue) and the data points at the output of the autoencoder when the full model (3) is used (Red). (Center Left) Data representation in the embedded domain when just the autoencoder is trained without the F(Z, C) term (Blue) and the full SEDSC model is used (Red). (Center Right) The absolute value of the recovered C encoding matrix when trained with the full model. (Right) Same plot as the previous column but with a logarithmic color scale to visualize small entries.
clustering, which involves 1) entrywise hard thresholding, 2) applying the shape interaction matrix method Costeira & Kanade (1955) C, and 3) raising C to a power, entry-wise. Likewise, many subsequent works on SEDS follow Ji et al. (2017) and employ very similar post-processing steps on C. As shown in Figure and Table there is little observed benefit for using SEDSC, as achieves comparable (or worse) performance than baseline methods in almost all settings when the post-procsssing of applied consistently (or not) across all methods.
Synthetic Data Experiments. Finally, to illustrate our theoretical predictions we construct simple synthetic dataset which consists of 100 points drawn from the union of two parabolas in R² where the space of the embedding is also R² We then train the model given in (3) with ((C) Ossc(C) ||C|| + + = 0). the encoder/decoder networks being simple single- hayden-layer fonnecco networks with 100 hidden units, and ReLU activations the hidden units. Figure 33 shows the solution obtained when we directly add a normalization operator to the encoder network which normalizes the output of the encoder have unit Frobenius norm over the entire dataset (Dataset Normalization). Additional experiments for other normalization schemes and description of the details of our experiments
be found in the Supplementary Material.
From Figure 3 one can see that our theoretical predictions are largely confirmed experimentally. Namely, one sees that when the full SEDSC model is trained the embedded representation largely as predicted by Theorem 2 with almost all of the embedded points (Left Center Red points) being close to the origin with the exception of two points, which are co-linear with each other. Likewise, the C matrix is dominated by two non-zero entries with the remaining non-zero entries only appearing on the log-scale color scale. We note that as this a very simple dataset (i.e., two parabolas without any added noise) one would expect most reasonable manifold clustering/learning algorithms to succeed; however, due to the deficiencies of the SEDSC model we have shown in our analysis trivial solution results.
4 CONCLUSIONS
We have presented a theoretical and experimental analysis of the Self-Expressive Deep Subspace Clustering (SEDSC) model. We have shown that in many cases the SEDSC model is ill-posed and results in trivial data geometries in the embedded space. Further, our attempts to replicate previously reported experiments lead us conclude that much of the claimed benefit of SEDSC is attributable to other factors such post-processing of the recovered encoding matrix, C. and not the SEDSC model itself. Overall, we conclude that considerably more attention needs be given to the issues have raised in this paper in terms of both how models for this problem are designed and how they are evaluated to ensure that one arrives at meaningful solutions and can clearly demonstrate the performance of the resulting model without other confounding factors.
Acknowledgments. The authors thank Zhihui Zhu and Benjamin Béjar Haro for helpful discussions in the early stages of this work. This work was partially supported by the Northrop Grumman Mission Systems Research in Applications for Learning Machines (REALM) initiative, NSF Grants 1704458, 2031985 and 1934979, and the Tsinghua- Berkleey Shenzhen Institute Research Fund.

---

Published as a conference paper at ICLR 2021
REFERENCES
Mahdi Abavisani and Vishal M Patel. Deep multimodal subspace clustering networks. IEEE Journal of Selected Topics in Signal Processing. (166):1601166) 2018.
Joao Costeira and Takeo Kanade. A multi-body factorization method for motion analysis. In IEEE International Conference on Computer Vision, pp. 1071-1076. IEEE, 1995.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 2790-2797, 2009.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions Pattern Analysis and Machine Intelligence, 35(11):2765-278. 2013.
Sergey loffe 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. In Advances Neural Information Processing Systems, pp. 24-33, 2017.
Yangbangyan Jiang, Zhiyong Yang, Qianqian Xu, Xiaochun Cao, and Qingming Huang. When to learn what: Deep cognitive subspace clustering. Proceedings of the 26th ACM international conference on Multimedia, pp. 718-726, 2018.
Yangbangyan Jiang, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. Duet robust deep subspace clustering. In Proceedings of the 27th ACM International Conference on Multimedia, pp. 1596-1604, 2019.
Mohsen Kheirandishfard, Fariba Zohrizadeh, and Farhad Kamangar. Deep low-rank subspace clus- tering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 864-865. 2020a.
Mohsen Kheirandishfard, Fariba Zohrizadeh, and Farhad Kamangar. Multi-level representation learning for deep subspace clustering. The IEEE Winter Conference on Applications of Com- puter Vision, pp. 2039-2048, 2020b.
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):1200-1333 2018.
Ruihuang Li, Changqing Zhang. Huazhu Fu, Xi Peng, Tianyi Zhou, and Qinghua Hu. Reciprocal multi-layer subspace learning for multi-view clustering. In IEEE International Conference Computer Vision, pp. 172-8180, 2019.
Guangean Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, and Yi Ma. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intel- ligence, 35(1):171-18) 2013.
Can-Yi Yi Lu, Hai Min, Zhong- Zhong-Qiu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. In European Conference Computer Vision, pp. 347-360, 2012.
N. Parikh and S. Boyd. Proximal Algorithms. Foundations and Trends in Optimization, 1(3):123- 231, 2013.
V. M. Patel and R. Vidal. Kernel sparse subspace clustering. In IEEE International Conference on Image Processing, pp. 2849-2853, 2014.
V. M. Patel, H. V. Nguyen, and R. Vidal. Latent space sparse subspace clustering. In IEEE Interna- tional Conference on Computer Vision, pp. 225-232. 2013.
V. M. Patel, H. V. Nguyen, and R. Vidal. Latent space sparse and low-rank subspace clustering. IEEE Journal Selected Topics in Signal Processing, 9(4):691-701 2015.
10

---

Published as a conference paper at ICLR 2021
Xi Peng, Jiashi Feng, Shijie Xiao, Jiwen Lu, Zhang Yi, and Shuicheng Yan. Deep sparse subspace clustering. arXiv preprint arXiv:1709.08374, 2017. 2017.
Daniel P Robinson, Rene Vidal, and Chong You. Basis pursuit and orthogonal matching pursuit for subspace-preservvnng recovery: Theoretical analysis. arXiv preprint 1etei9912...999 2019.
Mahdi Soltanolkotabi and Emmanuel J. Candès. A geometric analysis of subspace clustering with outliers. Annals of Statistics, 40(4):2195-2)) 2238, 2012.
Mahdi Soltanolkotabi, Ehsan Elhamifar, and Emmanuel J. Candès. Robust subspace clustering. Annals of Statistics, 42(2):669-66) 2014.
Xiukun Sun, Miaomiao Cheng, Chen Min, and Liping Jing. Self-supervised deep multi-view sub- space clustering. Asian Conference on Machine Learning, pp. 1001-1016, 2019.
Xiaoliang Tang, Xuan Tang, Wanli Wang. Li Fang, and Xian Wei. Deep multi-view sparse subspace clustering. In Proceedings of the 2018 VII International Conference on Network, Communication and Computing, pp. 115-119, 2018.
Manolis C. Tsakiris and René Vidal. Theoretical analysis of sparse subspace clustering with missing entries. International Conference on Machine Learning, pp. 4975-495544 4984, 2018.
René Vidal and Paolo Favaro. Low rank subspace clustering (LRSC). Pattern Recognition Letters, 43:47-61, 2014.
René Vidal, Yi Ma, and Shankar Sastry. Generalized Principal Component Analysis. Springer Verlag, 2016.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4)3395-416 2007.
Yining Wang, Yu-Xiang Wang, and Aarti Singh. A deterministic analysis of noisy sparse subspace clustering for dimensiionllty-reduee data. In International Conference on Machine Learning, pp. 1422-1431, 2015.
Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. Journal of Machine Learning Research, 17(12):1-41, 2016.
Yuan Xie, Jinyan Liu, Yanyun Qu, Dacheng Tao, Wensheng Zhang, Longquan Dai, and Lizhuang Ma. Robust kernelized multiview seff-representation for subspace clustering. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Shuai Yang, Wenqi Zhu, and Yuesheng Zhu. Residual encoder-decoder network for deep subspace clustering. arXiv preprint 110.5591., 2019.
Yingzhen Yang, Jiashi Feng, Nebojsa Jojic, Jianchao Yang. and Thomas S Huang. lo-sparse sub- space clustering. In European Conference Computer Vision, pp. 73 7-1774 2016.
C. You and R. Vidal. Subspace-sparse representation. Arxiv, 5507011077. 2015a.
Chong You and René Vidal. Geometric conditions for subspace-sparse recovery. In International Conference on Machine Learning. pp. 1585-1593, 2015b.
Chong You, Chun-Guang Li, Daniel P. Robinson, and René Vidal. Oracle based active set algorithm for scalable elastic subspace clustering. In IEEE Conference Computer Vision and Pattern Recognition, pp. 3928-3937, 2016.
Chong You, Chun-Guang Li, Daniel P. Robinson, and René Vidal. Is an affine constraint needed for affine subspace clustering? In IEEE International Conference on Computer Vision, 2019.
Meng Zeng, Yaoming Cai, Zhihua Cai, Xiaobo Liu, Peng Hu, and Junhua Ku. Unsupervised hyper- spectral image band selection based on deep subspace clustering, IEEE Geoscience and Remote Sensing Letters, 16(12): 10::-1881199 2019a.
11

---

Published as a conference paper at ICLR 2021
Meng Zeng, Yaoming Cai, Xiaobo Liu, Zhihua Cai, and Xiang Li. Spectral-spatial clustering of hyperspectral image based on laplacian regularized deep subspace clustering. In IGARSS 2019- 2019 IEEE International Geoscience and Remote Sensing Symposimm, pp. 2694-2697. IEEE, 2019b.
C. Zhang, S. Bengio, M. Hardt, and B. Recht. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
Changqing Zhang, Huazhu Fu, Qinghua Hu, Xiaochun Cao, Yuan Xie, Dacheng Tao, and Dong Xu. Generalized latent multi-view subspace clustering. IEEE Transactions Pattern Analysis and Machine Intelligence, 42(1):86 2018.
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 Conference on Computer Vision and Pattern Recognition, pp. 5473-5482, 2019a.
Tong Zhang, Pan Ji, Mehrtash Harandi, Huang Wenbing, and Hongdong Li. Neural collaborative subspace clustering. In ICML, 2019b.
Lei Zhou, Bai Xiao, Xianglong Liu, Jun Zhou, Edwin R Hancock, et Latent distribution preserv- ing deep subspace clustering. In 28th International Joint Conference on Artificial Intelligence. York, 2019.
Pan Zhou, Yunqing Hou, and Jiashi Feng. Deep adversarial subspace clustering. In IEEE Conference Computer Vision and Pattern Recognition, pp. 1556-1104,, 2018.
12

---

Published as a conference paper at ICLR 2021
5
PROOFS OF RESULTS IN MAIN PAPER
Here we present the proofs of our various results that we give in the main paper.
5.1 PROOF OF PROPOSITION
Proposition 1 Consider the objective in (3) and suppose (C) in ① is a function which achieves its minimum at C = 0 and satisfies (cC) < ((C), Vu E (0.1). ffr any choice of (Wa, We) and
TI, 12 E (0, 1) there exists (Wa, We) such that (x, We) TI (X, W.) and ( Wa) (Z, Wa) then the F term in (3) can be made arbitrarily small without changing the value of the loss function l. Further, if the final layer of the encoding network is csstively-homoggen
with degree p + O, such (Wa, We) will always exist simply by scaling the network weights of the linear (or affine) operator parameters.
Proof. Let (C, We: Wa) be an arbitrary triplet. For any choice of 7 E (0, 1), note the statement conditions require that there exists (C, We, Wa) which satisfy
Ö = PC
(X, W.) T We)
(15)
Φ Z, Wa) (Z, Wa).
Then, the function evaluated at We, Wa) is given by
{X, ( W. WCC Wa)) = f(X 4D (x) W.C,,
(16)
which is equal to l evaluated at (C, We. Wa). Moreover, the function F evaluated at (Č, We, Wa) given by
2 2g X, W.) - 2 (X, Wo + A0(WC)
(17)
0 X, W.) tx W. Wo) X0(C)).
Note that the above equation can be made arbitrarily small for choice of t, μ sufficiently small, completing the first statement of the result.
To see the second part of the claim, first note that the condition on the decoder that for all (0, 1) there exists Wa such that & ( Wa) pZ, Wa) - is trivially satisfied by all neural networks by simply scaling the input weights in the first layer of the decoder network by -5- As a result, we are left to show that there will always exist a set of encoder weights which satisfies the conditions of the statement. To see this, w.l.o.g. let &b (X, We) take the general form
(X, W.) = (AAM(X VV.), A, b))
(18)
where A(-,A, A. b) is an arbitrary linear (or affine) operator parameterized by linear parameters A and bias terms (for affine operators) b; ((X, W:) an arbitrary function parameterized by We (note that W. = {A, b, W.Y): )); and v is an arbitrary positively homogeneous function with degree p + 0. From this note that for any a > we have the following:
(<A((XX W.), aA, ab)) = ((aA(M(X W.), A,)) = a = (<A(N A,).A,)) b)).
(19)
where the first equality is due basic properties of linear equality is due to positive homogeneity. As result, for any choice of T1 E (0. 1) we can choose
affine) operators and the second
scaling 7/ /P achieve that for parameters W. = (7) 1/P 1/PA, A, 1/b, We) we have & (X, W.) 7 F..... (X, We), completing the result.
5.2 PROOF OF THFOREM 1
Theorem L Consider the following optimization problems whichhointly optimize over and C:
(P1) min CZ, s.t. 2 C,
(P2)
min ( C) s.t. Z 2 Wi
(20)
C.
13

---

Published as a conference paper at ICLR 2021
Then optimal values for C for both (P1) and (P2) are given by
C' E arg mig 2 o +
(21)
Moreover, for any optimal C², let r be the multiplicity of the smallest singular value of C and let Q RNxx xr be an orthonormal basis for the subspace spanned by the left singular vectors associated with the smallest singular value of C - Then we have that optimal values for Z are given by:
[B : B = 7}
Min (C* - I) > 0
(PI)
[B [B }}
min (C* - I) = =0
Z' E (BQ : B B nB), B
[B: [ E d
Vi}
miin (C* -1)
(P2)
[ B Z Z ViJ
miin (C* - 1)
(22)
Proof. The objective F(Z, C) can be reformulated as
1 F(Z, C) (CC -
1 "TAZ0-=+((CCC00411770000----1111 (CCC::CCCTTTNO000-1-2//CCCCC----
(23)
where recall Z' denotes the 5thh row of Z. If we add the constraints on Z we have the following minimization problems over Z with C held fixed:
d min 2
Z'C - 2 1=1
1) (Z)) T s.. ZEZ 2 (P2)
2T
(P1)
(24)
Note that if we fix the magnitude of the rows, 1Z k, for any k E Rd k 2 0, Σ k, 2T
for (PI) and k E Rd, k, 2 r/d for (P2) and optimize over the directions of the rows, then the minimum is obtained whenever Z is in the span of the eignevectors of (C (C smallest eigenvalue, which implies that all the rows of optimal Z matrix must lie in the span of Q, where Q E Xxr is an orthonormal basis for the subspace by the left singular vectors of C associated with the smallest singular value of C I, which has multiplicity r.
with
As a result, we have that optimal values of Z must take the form Z = BQ T for some B E Rdxr. Further, note that the following also holds:
1
F FBQQ T, C) BBQ (C I) -) 1) QBBBB + AO(C)=
2
(25)
1
2 0
min (C- - I)tr BB ) + XB(C) =
2 min (C - BIB (C-I)
+ AO(C).
The constraints for B are then seen by noting ZZT T = BQ QB = BB so 7 P
tr (ZZ = tr = [B and Z (ZZ )x, = (BB )r, = (B
)..
B P.
and if miin (C* - I) then minimizing 25 w.r.t. B subject to the constraints on Z gives that
B 7 is optimal.
5.3 PROOF OF THEOREM
Theorem
2. Optimal solutions to the problems
(P1) min |[]l, s.t. diag(C) = ZC, |
2 T
(26)
Z.C
(P2) min Cll s.t. diag(C) 0, zc,
|
Vi
(27)
Z.C
characterized by the
0 1
0
1
0 0
0
(Z",C") E 11z z 02xN-2] P] x PT
0
0
P
(28)
0
14

---

Published as a conference paper at ICLR 2021
where P E RNNN is arbitrary dignet-permutationn matrix and E R is an arbitrary vector which satisfies | p 2 T for (P1) and z 2 T2d2)), vi E [1, d] for (P2).
Proof. As we observed from the proof of Theorem [ if C I has left null-space we can choose an optimal Z to have its rows in that null-space (and this also clearly implies we have Tiiu (C- = 0). Also note that when min (C- I]
this corresponds to the case where Z ZC > Z(I
C) 0. Further, note that if q is non-zero vector in the left null-space of C - I we have that
(C- - = 0 = q C = q T, which implies that if we take q to be all-zero except for its entry, then this would imply that C,, must be non-zero, which would violate the dCa constraint, so any vector q in a left null-space of - for a feasible matrix must have at least two non-zero entries. As result, solving (5) with the constraint m (C - I) = 0 is equivalent to the following problem:
min [C| s.t. q qT - = 0, (Ca = 0, || o 2 2.
(29)
C.q
where ||- llo denotes the lo pseudo-nore norm of vector defined the number of non-zero entries in vector. To first minimize w.r.t. C with a fixed q, we form the Lagrangian:
min (L(C,A,T) r = |C]| + (A, (I )²) + (Diag(T), C)}
(30)
C
min ||C|| + (qA -Dag C) + (A, q) = (A, q) - a(l T Diag Il) S 1), (31)
C
where A E RN and I E EN are vectors of dual variables to enforce the (I -I-C' 1-CT) CTqqq 0 and the diag( C) = 0 constraints, respectively. This gives the dual problem
max (A, q) s.t. ||qA T lil 1 = max (A. s.t. |4,4,1 < 1 Vi + j}. A,
(32)
We note that (32) is separable in the entries of A, so if we define { sorts the absolute values of the entries of q in descending order, qq. 2 1q:a1 Σ ... 2 g I. one can easily see that an optimal choice of A is given by
k- to be the indexing which
A; = (ggn(g:)))
sgn(ge))
96
A
Ak 12 = (A
(33)
4ig
9
9ig
k=2
If we now minimize the above w.r.t. q. note that the optimal value of the dual objective given by the above equation invariant w.r.t. scaling the q vector by any non-zero scalar, so we can w.l.o.g.
assume that 1q: = 1 and note that this implies that problem (29) is equivalent to the following
optimization problem over the magnitudes of q if we define pk 4
N
min Mi
+ P2
+
Ps s.t. 1 12 P2 2
2 PN 2 O.
(34)
P2
Now, note that for non-negative scalar 2 0 the minimum of a + a is achieved at a = 1, so one can clearly see that the optimal value for the above problem achieved at P2 = and pa = 0, Ak E [3, NJ. From this we have that an optimal q for 29 must have exactly two non- zero entries and the non-zero entries must be equal in absolute value. Further, this also implies that ||C*||| 2, and because we must have q C* T. if we scale q to have +1 for its two non-zero entries, we then have ||q TC || =
||q/] = 2 = |[ so if we let (i,j) index the two non-zero
entries of q we have:
2 = |/q 1² = ||sgn( (q:)
(q:) (C*)' < I(C*))+++( S ||C*||, = 2. (35)
This implies that all the non-zero entries of C* must lie in rows and j. and if there any overlap in the non-zero support of these rows the signs must match after multiplication by sgn(q:) and sgn(q,). However, since q C must equal q (which is zero everywhere except for entries i and j) and the diagonal of C' must be zero, the only way this can be achieved is for the two rows to have non-overlapping non-zeri support, proving that the only non zero entries of C must be Ci,y and C,., which take values in {-1, 1}. depending
the choice of the signs for qi and qj. The result is completed by noting that since we require Z' = Z C*, then Z and Z must be equal to within a sign-flip depending on the choice of the signs of the q vector.
15

---

Published as a conference paper at ICLR 2021
5.4 PROOF OF THEOREM
Theorem 3 Optimal solutions to the problems
(P1) min
Clls, s.t. Z ZC, |Z|| 2T
(36)
Z.C
(P2) min
Clls, s.t. Z Zc, |Z 2 Vi,
(37)
Z.C
where |[C|s, is any Schatten-p norm on C, are characterized by the
(Z" E {(z (by q IN.. |/|/// = =1
(38)
where Bdd is arbitrary vector which satisfies ||z 2 for (P1) and 2² 2. fir (P2).
Proof. To begin, by the same arguments as in Theorem 2 we consider an optimization problem
similar to 29 but for ((C) [Clss, being any Schatten-p norm and with the ||ql|o constraint
replaced by a * O constraint:
min |[i|s, s.t. - - a 0.
(39)
C.q
Again forming the Lagrangian for with q fixed we have:
min (L(C, Clls, (A, (1- C )a)a)
(40)
min [Cl|s, - (qAT, C) + (A, q) = (A, q) 5(1lqA 118, S (41) C
which implies the dual problem is: A
max(A, q) s.t. /وq1 T 1
(42)
where || I1s, denotes the dual norm. Note that for any Schatten-p norm, the dual norm is again Schatten-p norm, but since we only evaluate the norm on rank-1 matrices this is equal to the Frobenius norm for all values of p. As a result we have for all choices of Schatten-p norm that the dual problem is equivalent to:
max (A, ②) s.t. [lqATI: s 1) = max (A a) s.t. |||//|/|| S 1} A
(43)
From the above, one can easily see that the optimal choice for A is given as A = | and the optimal objective value is 1. Further note that from primal optimality in (41) we must have that q(A*)T E I|,, which implies that (C*, q(A"))> = |C*'ls,,IqqAA> l|s = ||C* = 1. As result, we have that C ((A*) by the Cauchy-Schwer [Aq(A*)T || 1. Thus since C* is rank-1 matrix then C* I can only have one singular value equal 0, so all the rows of Z" must be equal to a scaling of q. Given this structure for Zt the result then follows, where we also recall that C* = 1, which implies the constraints on in the statement.
inequality and the fact that
5.5 PROOF OF THEBRRM
We now present the proof for Theorem Lemma which will be helpful.
Before proving the main result we first prove a simple
Lemma For given matrix Z d and vector Rd such that [Zel| Vi and
| = T, let E [0, N be the number of columns in which are equal to z to within a sign-flip
(i.e., Z, +z). Then, if k 2 1 the following holds:
min {||c]/ s.t. z = Zc} =1
(44)
c
and c + Z; =2.
Further, if k 0 we also have
min (||c]/ s.t. 2 Ze} > 1
(45)
(where we use the convention that the objective takes value oo if Ze. has no feasible solution.)
16

---

Published as a conference paper at ICLR 2021
Proof.
Without loss of generality, assume the columns of Z are permuted so that Z has the form:
Z = zs Z
(46)
where s E {-1,1} is a vector with & E [0, M elements each taking value -1 or 1, and Z E
[d k) contains all the columns of Z which are not equal to =z.
First we consider the k 2 1 case and note that the Lagrangian of (44) is given as: L(c, A) = ||c]] + (A, Ze)
(47)
Now minimizing L w.r.t gives
min ||c||2 - (Z A, = 5 | A 1
(48)
which gives that the dual problem to
(with k: 2 1) is given by
max(A, z) S.t. I|A T x0
max(A, s.t. {( 2,) 11, [IE
A
(49)
max(A, 2) s.t. (A,, 2)1 1 KA,, Z,I 1 Vi E N R.]
A
where the final equivalence is due to the special structure of Z in (46). Clearly from (49) and the fact that | F | T, Vi it is easily seen that an optimal A is any vector such that (A*, .2) = 1, so as a result we have that the optimal solution to the problem (44) has objective value 1. Further, note that when & 2 I. then due to the triangle inequality and the fact that all the vectors in Z have equal norm we can only achieve z = Ze with |c*I|a = if all the non-zero entries of c are in the first & entries and the sign of any non-zero element of c" must satisfy sgn(c.)
8,, i [1.
To see that (45) is true, first note that an optimal solution to 449 with is 2 1 is to choose A = zT and that because Z, 전 =z, Vi we have (Z,, = (Z,,
|Z,ll= ||ZT -11 1. Further, note that the problem in (45) (with & = 0) will have an equivalent dual problem to (49). with the (A, 2) S 1 constraint removed, which shows the inequality, as we always take = azr-2 for some a > 1 and remain dual feasible, giving a dual value (and hence optimal objective value) for 45)
strictly greater than 1.
With this result we are now ready to prove Theorem 4
Theorem 4 Optimal solutions to the problem
min Z.C
||Clla s.t. diag(C) = 0, Z = ZC, 7Z, 13-- = Vi
(50)
must have the property that for any column in Z", Z there exists another column, Z (i + j), such that Z = 88,3 Zi where 8ij E (-1, Further, || [ || = 1 Vi and C.2 # 0 Z:- = +
Proof. First, note that any Z* which satisfies the conditions of the Theorem achieves optimal objec- tive value with |C; 1 1, Vi and Ct,, # 0 = Z = directly from Lemma since when we are finding an optimal C; encoding for column Z there must exist another column in Z which is equal to Z to within sign-flip (k: 2 1 in Lemma D.
To show that this is optimal, we will proceed by contradiction and assume we have a feasible pair of matrices (Z, C) which does not satisfy the conditions of the Theorem but ||C|], < N = -C*Il- Note that because Z does not satisfy the conditions of the Theorem this implies that at least one column of must be distinct (i.e., 3i : 2, + +Zj, Vj A i). As a result, for any column Z, which is distinct we must have ||C]]] > 1 from Lemma ( = 0 case). If we let I denote the set of indices of the distinct columns in Z and I the compliment of I we then have
||č,ll
Σ I,, + Σ J, 1|1
(51)
iEI
jEZ
Σ
C + |I9
(52)
IEI
(53)
where the first equality comes from noting that for any 2, j E I corresponds to the k 2 situation in Lemma and the inequality comes from noting that any Z, i E I corresponds to the k = situation in Lemma and the fact that I 2 1. We thus have the contradiction and the result is completed.
17

---

Published as a conference paper at ICLR 2021
5.6 PROOF OF PROPOSITION 2
2 Consider encoder and decoder networks with the form given in (14) Then, given any dataset X RdxxN where the linear operators in both the encoder/decoder can express identity on X and any T > O there exist network parameters (Wer Wa) which satisfy the following:
Proposition
Embedded points are arbitrarily close: [X,, We) - DE (X,, Wc)l = ((, and Ve > 0.
2. Embedded points have norm arbitrarily close to r: 2 (X,; We)l - S Vi and Ve > 0.
3. Embedded points can be decoded exactly: D X,, We), Wa) X,, vi.
Proof. To begin, let (W:, W and (W), W be choices of linear operator parameters such that W = W X X which always must exist since the operators can express identity on X. Now, for an arbitrary a > O let b. be any vector such that a XX ; + by is non-negative for all i (note that this is always possible by taking bj. to be a sufficiently large non-negative vector). Note that now if we choose by 0 we then have vi and all 8 >> 0:
(54) where the ReLU function becomes identity operator due the fact that have all non- negative entries. Likewise, can choose by be an arbitrary vector such that (B-1W) + BW?)! bj is non-negative for X,, so we choose b2 -aa- W + byj we then have:
(a b + D (a (a + b = a3x; + SW26
(a W2ll0- + SW26 + b/1+ + b3
=(a W2 + sWbb + b + by
(55)
WW (3 (WW + bJ 62
=X;
So as a result we have constructed a set of encoder/decoder weights which satisfies the third condi- tion of the statement. Further, the embedded points in this construction of the form
Z: = o;3X; + W
(56)
so since we can form such construction for an arbitrary 0 and O can choose a - arbitrarily small and = T give that all the embedded points Z; are arbitrarily close to the point T W w which completes the result.
ADDITIONAL RESULTS AND DETAILS
Here we give few additional results which expand on results given in the main paper along with extra details regarding our experiments.
6.1 EXPERIMENTS WITH REAL DATA
In addition to the results we show in the main paper, we also present additional experimental results on real data. In particular Figure (Left) shows the magnitude of the embedded representation. Z. using the original code from Ji et al. (2017) to solve model (3) using the YaleB dataset (38 faces). Note that the optimization never reaches a stationary point with the magnitude of the embedded representation continually decreasing (as predicted by Proposition D Additionally, if one looks at the singular values (normalized by the largest singular value) for the embedding of data points from one class (Right), then training the autoencoder without the F(Z, C) term results in geometry that closer to a linear subspace. Further, the raw data is actually closer to a linear subspace than after training the full SEDSC model (comparing Red and Blue curves). Interestingly, the fact that the autoencoder features and raw data is closer to a linear subspace than SEDSC is also consistent with the clustering performance show in Table where for the setting without the post- protesroesssing the autoencoder-only features achieve the best clustering results, followed by the raw data, followed by SEDSC.
18

---

Published as a conference paper at ICLR 2021
Norm of Z
Singular values of one class
10a
Raw
AE
160000
SEDSC
140000
120000
10-1
100000
80000
60000
10-2
50
100
150
200
300
350
400
10 15
Iterations/50
Index of Singular Value
Figure 4: Experiments on Extended Yale dataset. (Left) The norm of the embedded representa- tion as training proceeds. (Right) The singular values of the embedded representation of points from one class, normalized by the largest singular value. (Raw) The singular values of the raw data. (AE) The singular values of the embedded representation from an autoencoder trained without the F C) term. (SEDSC) The singular values of the embedded representation from the full SEDSC model
Details of experiments with real data. We use the code provided by the authors of et al. 2017 3
The code implements the model in (3) with ((C) 2 [[|| and ((::)) being the squared loss. The training procedure, as described in Ji et al. (2017). without the (ZZ C) term. Such pretrained models for each of the three datasets are also provided alongside with their code. Then, the encoder and decoder networks of SEDSC are initialized by the pre-trained networks and all model parameters are trained via the Adam optimizer.
involves pre-training an antoencoder network
The implementation details of the three methods reported in Figure 2 and Table I namely Raw Data, Autoenc only and Full SEDSC,
follows. For Raw Data, solve the model in ① with ((C) C and chosen in the set {0.5, 1,2, 5, 10, 20, 50, 100, 200, 500) that gives the highest averaged clustering accuracy over 10 independent trials. For Autoenc only, encoder and decoder networks to initialize SEDSC, then freeze the encoder and decoder networks and use Adam optimize the variable only. The results for Full SEDSC are generated by running the code as it is. Finally, the same post-processing step is adopted for all three methods (i.e., we do fine-tune for Raw Data and Autoene only).
the pretrained
6.2 EXPERIMENTS WITH SYNTHETIC DATA
In addition to the results shown in the main paper we additionally conduct similar experiments with synthetic data for the Instance Normalization and the Batch/Channel Normalization scheme.
Details of experiments with real data. For the Dataset and Batch/Channel normalization experi- ments we directly add a normalization operator to the encoder network which normalizes the output of the encoder such that the entire dataset has unit Frobenius norm (Dataset Normalization) each row of the embedded dataset has unit norm (Batch/Channel Normalization) before passing to the self-expressivg layer. For the Instance Normalization setting add the regularization term pro- posed in Peng al. (2017) with the form 72 Ei= (Z. Z; 1)² the objective in (3). We regularization hyper-paramettrs (A, (10- 4 2) for all cases and 72 10-4 for the Instance Normalization case.
We first pretrain the autoencoder without the F(Z. C) term (i.e., = and C fixed at I), and we initialize the C matrix to be the solution to I using the Z embedding from the pretrained autoencoder. Following this we perform standard proximal gradient descent (Parikh & Boyd 2013) on the full dataset, where we take a gradient descent step on all of the model parameters for the full objective excluding the 6( ((C) term, then we solve the proximal operator for o (C.. Figure 5 shows the results of this experiment, where we plot the original dataset along with the reconstructed output of
https://github/ http:/ichhu.cooooaaooaaa 1900/199900/0000 /0eepeeep---- subspace-cluseeeeeece networrk
19

---

Published as a conference paper at ICLR 2021
Original Data Domain
Embedded Data Domain
[C] - log color scale
Instance
-02
AutoEncoder Sef
04-
Dataset
3
Original Data
-42
-42
Batch Norm
60-
-02
0.2 -35 -24 -22
Showing results for the synthetic dataset for three normalization schemes (along the rows). Instance Normalization (top); Dataset Normalization (center); Batch/Channel Normalization (bottom). The columns are the same described in the main paper. (Left) Original data points (Blue) and the data points the output of the autoencoder when the full model (3) is used (Red). (Center Left) Data representation in the embedded domain when just the autoencoder is trained without the FZZ,Cr C) term (Blue) and the full model is used (Red). (Center Right) The absolute value of the recovered C encoding matrix when trained with the full model. (Right) Same plot as the previous column but with logarithmic color scale to visualize small entries.
Figure 5:
the autoencoder (Left), the embedded representation after pretraining the autoencoder (Left Center- Blue) and after fully training the model (Left Center-Red), the absolute value of the final C matrix (Right Center), and the same plot with logarithmic color scale to better visualize small entries (Right).
that theoretical predictions are largely confirmed experimentally. Namely, first examining the Batch and Dataset normalization experiments one sees that when the full SEDSC model is trained the embedded representation is very close
From Figure 5 one
predicted by Theorem 2. with almost all of the embedded points (Left Center Red points) being near the origin with the exception of two points, which are co-linear with each other. Likewise, the C matrix is dominated by two non-zero entries with the remaining non-zero entries only appearing on the log-scale color scale. Further, the Instance normalization experiment also largely confirms our theoretical predictions, where all the points are co- lo-linear and largely identical copies of single point.
20


Reviews:
[{"review_id": "tJBQZJ5M3zI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper critiques the commonly-used self-expressive cost function used to learn embeddings for deep subspace clustering. The authors point out that the empirical improvements obtained by deep self-expressive subspace clustering may be artifacts of post processing on the learned affinity matrix. They then theoretically characterize the optimal solutions to a variety of cost functions/normalization procedures used within the deep subspace clustering literature, showing that these encourage points to be mapped to a singleton set up to a sign change.\n\nThe theoretical contributions of this paper are significant, and the critique of deep self-expressive subspace clustering is timely and important. A survey of \"shallow\" subspace clustering methods shows that the alleged performance improvements obtained by deep subspace clustering typically amount to parameter tuning or post processing, as shallow methods often perform at least as well when properly tuned. The paper provides solid evidence that researchers should think more deeply when designing loss functions for unsupervised learning with neural networks. Empirical results are included that verify the theoretical contributions of this work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "bIhQxSherAa", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper calls into question the significance of previous results on Self-Expressive Deep Subspace Clustering (SEDSC) models, which are touted as successful extensions of the linear subspace clustering (using the self-expressive property) to non-linear data structures. The authors present a set of theoretical results that indicate that the standard formulations of  SEDSC are generally ill-posed. Even with added regularizations, it is shown that such formulations could very well yield trivial geometries that are not conducive to successful subspace clustering. \n\nComments: \nAlthough I have not fully checked the proof of the theoretical results, I believe this is a solid piece of work as it sheds light on shortcomings of SEDSC formulations using a rigorous theoretical approach. The authors verify their arguments using a good set of experiments. The findings also suggest that much of the claimed success of such models can in fact be attributed to post-processing of the encodings rather than the validity of the model. \n\n- The paper has a limited scope as it raises concerns about an existing deep Subspace Clustering algorithm. I am not sure whether this algorithm is widely adopted and how significant it is -- the paper does also look at a class of similar formulations based on different regularizations. As such, I feel the paper addresses a somewhat limited audience and the impact of the work appears somewhat limited.\n\n- Other than the limited scope, I do not see major weaknesses in this work, and I think the authors did a good job explaining the main ideas. \n\n- The paper is hard to read for people who have not worked in closely related areas. \n\n- The findings of this question beg the question -- which the paper does not attempt to answer -- as to whether there exist some other forms of regularizations for such models that would promote geometries of the embeddings that are conducive to successful clustering. \n\nI believe this is a good paper worthy of being considered. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GcprFO47VMR", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the flaws associated with extending subspace clustering methods to the nonlinear manifolds scenario. In particular, the authors demonstrate that the optimization problem solved due to the extension can be ill-posed and thus lead to solutions which are degenerate/trivial in nature. The paper also showed that the performance benefits often associated with the Self-Expressive Deep Subspace Clustering techniques are potentially due to post-processing steps and other factors rather than due to the efficacy of these methods themselves.\n\nOverall the outline of the paper is good and I found the discussed problem informative. Few aspects were unclear to me (refer below). \n\n1) In section 2, the authors discuss positively-homogeneous functions i.e. (leaky) Rectifier Linear Units and how it effects the statement in Proposition 1. I would like to understand how Proposition 1 relates to other activation functions i.e. the Hyperbolic Tangent (tanh) and Sigmoid functions for example. In general, given the latter activation functions are not positively-homogeneous and have disparate saturation/non-saturation regions, can we extend the analysis to these activation functions and make the theoretical parts of the paper more generic ? \n\n2) In section 2.1, the authors talk about how Auto-encoders do not necessarily impose significant constraints on the geometric alignment of points. Are the authors aware of techniques like TopoAE and other state-of-the-art VAE/GAN and generative model variants which use some form of regularization to allow for topology modeling etc. and/or can produce results which achieve the above ? Did the authors consider this ?\n\n3) How do the authors quantify which encoder-decoder architectures are \"reasonably expressive\" ? Does any constraint as part of the objective function hamper this or are they referring to more specific constraints ?\n\n4) In sections 2.1 - 2.2, the authors mention that to remove trivial solutions the magnitude of the representations should be greater than some minimum value. What is this minimum value and how can we compute it efficiently ?\n\n5) In section 2.2, the authors briefly talk about how optimal solutions to the optimization problem may exist which have zero mean. How often do the computed optimum values fall in this category or in general are degenerate or trivial ? My point is existence of degenerate solutions need not mean that our optimization process will actually end up with these degenerate/trivial solutions. We typically can add constraints (which act like a prior and factor in the objective) and thus push our final solution away from degenerate/trivial solutions. \n\nI felt that the paper points out an important issue but if the authors could provide a general solution which helps ameliorate the issue (some general directions or even providing rudimentary results for one of the these directions) could have made the their contribution much more stronger. Overall I like the paper and the arguments made even though I have some inhibitions with regards to the scope of the contribution given the problem addressed is so specific.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BLAIcxu4lJd", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Pros:\n1)\tAuthors theoretically studied a class of self-expression deep subspace clustering methods and found that the optimization problem is typically ill-posed.\n2)\tVarious normalization approaches are studied, including dataset and batch/channel normalization, and instance normalization. However, even with these normalizations, the optimal embedded data geometry is still trivial in various ways.\n3)\tAuthors conducted experiments on real and synthetic data to further verify the theoretical conclusions. \n\nCons:\n1)\tAlthough authors uncovered the ill-posed issue in existing SEDSC methods, it is more interesting to see how the ill-posed issue can be resolved or alleviated. A proper working solution can further improve the quality of this paper.\n2)\tThe theoretical results seem mainly focusing on (3) with autoencoder regularization. Authors might want to specify the extension of the results to (2) in a more general form. Similarly, the discussion of various SEDSC methods cited in Section 1.1 in terms of the discovered results is important.\n3)\tAuthors mentioned the solutions are optimal in many places of this paper. From the perspective of the nonlinear optimization problems, it is not proper to say “optimal solutions”.  \n\nI change my rating after looking at authors response. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors carefully study a class of unsupervised learning models called self-expressive deep subspace clustering (SEDSC) models,  which involve clustering data arising from mixtures of complex nonlinear manifolds. The main contribution is to show that the SEDSC formulation itself suffers from fundamental degeneracies, and that the experimental gains reported in the literature may be due to ad-hoc preprocessing.

The contributions are compelling, and all reviewers appreciated the paper. Despite the paper being of somewhat narrow focus, my belief is that negative results of this nature are useful and timely. I recommend an accept.
Decision: Accept (Poster)