1

Subspace Clustering using Ensembles of
K -Subspaces

arXiv:1709.04744v1 [] 14 Sep 2017

John Lipor, David Hong, Dejiao Zhang, and Laura Balzano
Department of Electrical and Computer Engineering
University of Michigan, Ann Arbor
{lipor,dahong,dejiao,girasole}@umich.edu

Abstract
We present a novel approach to the subspace clustering problem that leverages ensembles of the K-subspaces (KSS) algorithm
via the evidence accumulation clustering framework. Our algorithm forms a co-association matrix whose (i, j)th entry is the
number of times points i and j are clustered together by several runs of KSS with random initializations. We analyze the entries
of this co-association matrix and show that a naïve version of our algorithm can recover subspaces for points drawn from the
same conditions as the Thresholded Subspace Clustering algorithm. We show on synthetic data that our method performs well
under subspaces with large intersection, subspaces with small principal angles, and noisy data. Finally, we provide a variant of
our algorithm that achieves state-of-the-art performance across several benchmark datasets, including a resulting error for the
COIL-20 database that is less than half that achieved by existing algorithms.

I. I NTRODUCTION
In modern computer vision problems such as facial recognition [1] and object tracking [2], researchers have found success
applying the union of subspaces (UoS) model, in which data vectors lie near one of several subspaces. Under this model,
the goal is to simultaneously identify these underlying subspaces and cluster the points according to their nearest subspace.
Algorithms designed to solve this problem fall under the category of subspace clustering, a topic that has received a great deal
of attention in recent years [3] due to its efficacy on real-world datasets such as the Extended Yale Face Database B [4] and
the MNIST handwritten digit database [5].
One of the earliest approaches to solving the subspace clustering problem involves an iterative method in the spirit of
K-means, known as K-subspaces (KSS) [6], [7], [8], which alternates between assigning points to clusters and estimating the
subspace basis associated with each cluster. As this algorithm is only guaranteed to converge to a local minimum, in practice
one runs many instances of the algorithm and chooses the final clustering as the one that produces the minimum cost. Although
its empirical performance is limited, KSS continues to serve as a benchmark for subspace clustering algorithms, in part due
to its computational efficiency and simplicity. Therefore, a deeper understanding of this method is an important contribution
in the area of subspace clustering and a contribution of this paper.
While the KSS cost function and alternating algorithm are perhaps the most natural approach for the subspace clustering
problem, it is known that there is a set of initializations of nonzero measure from which the algorithm will convergence to a
point other than the global minimizer.1 Our key observation is that even those “bad” initializations very commonly give some
partially-correct clustering behavior and may be combined to form a more accurate clustering algorithm.
Our contributions are as follows. We introduce a novel application of the well-known evidence accumulation clustering
framework [9] that leverages ensembles of the KSS algorithm to perform subspace clustering. By combining the results of
many random initializations of KSS, this algorithm obtains an affinity matrix (known as a co-association matrix), to which
we apply spectral clustering. We provide theoretical guarantees regarding the resulting affinity matrix that lead to recovery
guarantees for the subspace clustering problem. We show that our method is extremely effective on both synthetic and real
datasets; we show on synthetic data that our method has superior performance for subspaces that are extremely close together.
Further, we show that a variant of our algorithm achieves state-of-the-art performance on several real datasets, including error
on the COIL-20 image database and full Yale B database that are 24% and 54% better than state-of-the-art, respectively. Finally,
since our method relies on multiple independent initializations, it is inherently parallelizable. To the best of our knowledge,
we provide the first theoretical guarantees characterizing the co-association matrix resulting from evidence accumulation, as
well as the first recovery guarantees for any variant of the KSS algorithm.
II. P ROBLEM F ORMULATION & R ELATED W ORK
Consider a collection of points X = {x1 , . . . , xN } in RD belonging to a union of K subspaces S1 , . . . , SK having dimensions
d1 , . . . , dK . Let X ∈ RD×N denote the matrix whose columns are the elements of X . The goal of subspace clustering is to
label points in the unknown union of K subspaces according to their nearest subspace. Once the clusters have been obtained,
the corresponding subspace bases can be recovered using principal components analysis (PCA).
1 We

prove this fact for the simple case of two one-dimensional subspaces in R2 in Appendix B.

2

Most state-of-the-art approaches to subspace clustering rely on a self-expressiveness property of the data, which informally
states that points in the UoS model can be most efficiently represented by other points within the same subspace. These
methods typically use a self-expressive data cost function that is regularized to enforce efficient representation as follows:
min
Z

2

kX − XZkF + kZk
diag(Z) = 0,

subject to

where kZk may be the 1-norm as in sparse subspace clustering (SSC) [10], nuclear norm as in low-rank representation (LRR)
[11], or a combination of these and other norms. An affinity/similarity matrix is then obtained as |Z|+|Z|T , after which spectral
clustering is performed. Other terms are considered in the optimization problem to provide robustness to noise and outliers, and
numerous recent papers follow this framework [12], [13], [14], [15]. Efficient solutions to this problem based on orthogonal
matching pursuit and elastic-net are presented in [16], [17]. Other approaches include thresholded subspace clustering (TSC)
[18], in which an affinity matrix is formed by finding nearest neighbors of points in terms of spherical distance, and greedy
subspace clustering (GSC) [19], which greedily builds subspaces in order to form an affinity matrix. In all cases, spectral
clustering is performed as the final step to obtain cluster labels.
In contrast to the above methods, KSS seeks to minimize the sum of residuals of points to their assigned subspace, i.e.,
min
C,U

K
X

X

k=1 i:xi ∈ck

xi − Uk UkT xi

2
2

,

(1)

where C = {c1 , . . . , cK } denotes the set of estimated clusters and U = {U1 , . . . , UK } denotes the corresponding set of
subspace bases. Beginning with an initialization of K candidate subspace bases, KSS proceeds in an alternating fashion by
(i) clustering points via nearest subspace and (ii) obtaining new subspace bases by performing PCA on the points in each
cluster. The algorithm is computationally efficient and guaranteed to converge to a local minimum [6], [7]. As with K-means,
the KSS output is highly dependent on initialization. It is typically applied by performing many restarts and choosing the
result with minimum cost (1) as the output. This idea was extended to minimize the ℓ1 norm in [20], where a method for
intelligent initialization is also proposed. In [21], the authors use an alternating method based on KSS to perform online
subspace clustering in the case of missing data. Most recently, in [22], the authors propose a novel initialization method based
on ideas from [23], and then perform the subspace update step using gradient steps along the Grassmann manifold. While this
method is computationally efficient and improves upon the previous performance of KSS, it lacks theoretical guarantees.
Ensemble methods have been used in the context of general clustering for some time and fall within the domain of consensus
clustering, with an overview of the benefits and techniques given in [24]. The central idea behind these methods is to obtain
many clusterings from a simple base clusterer, such as K-means, and then combine the results intelligently. In order to obtain
different clustering results from each base clustering, diversity of some sort must be incorporated. This is typically done by
obtaining bootstrap samples of the data as in [25], [26], subsampling the data to reduce computational complexity as in [27],
or performing random projections of the data [28]. Alternatively, the authors of [29], [30] use the randomness in different
initializations of K-means to obtain diversity, which is the approach we take here for subspace clustering. After diversity is
achieved, the base clustering results must be combined. The evidence accumulation clustering framework is laid out in [9], in
which results are combined by voting, i.e., creating a co-association matrix A whose (i, j)th entry is equal to the number of
times two points are clustered together. A theoretical framework for this approach is laid out in [31], where the entries of the
co-association matrix are modeled as Binomial random variables. This approach is studied further in [32], [33], in which the
clustering problem is solved as a Bregman divergence minimization. These models result in improved clustering performance
over previous work but are not accompanied by any theoretical guarantees with regard to the resulting co-association matrix.
Further, they are not specifically designed to consider the case where the data are generated from the UoS model.
In the remainder of this paper, we apply ideas from consensus clustering to the subspace clustering problem. We describe
our ensemble KSS algorithm and its guarantees and demonstrate the algorithm’s state-of-the-art performance on synthetic and
several real datasets.
III. E NSEMBLE K -S UBSPACES A LGORITHM & G UARANTEES
In this section, we describe our method for subspace clustering using ensembles of the K-subspaces algorithm, which we
refer to as Ensemble K-subspaces (EKSS).
EKSS leverages the fact that for several runs of KSS, each random initialization results in some partially correct clustering
information. We therefore run several random initializations of KSS and form a co-association matrix using the results of each
run, after which we apply spectral clustering. Our theoretical results imply that even if the data come from generative subspaces
with arbitrary positioning, the algorithm outputs a perfect clustering, as long as the maximum subspace affinity (defined below
in Eq. (2)) is bounded and the points are drawn uniformly from the true subspaces without noise. For noisy data, the final
affinity matrix contains no false connections between points.
In more technical detail, our EKSS algorithm proceeds as follows. For each of b = 1, . . . , B base clusterings, we obtain
a cluster estimate C (b) from a single run of KSS with a random initialization. For each b such that the points xi and xj are

3

Algorithm 1 E NSEMBLE K - SUBSPACES (EKSS)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

¯ candidate dimension, K: number of
Input: X = {x1 , x2 , . . . , xN } ⊂ RD : data, K̄: number of candidate subspaces, d:
output clusters, q: threshold parameter, B: number of base clusterings, T : number of KSS iterations
Output: C = {c1 , . . . , cK }: clusters of X
for b = 1, . . . , B (in parallel) do
iid
¯
U1 , . . .n, UK̄ ∼ Unif(St(D, d))
Draw K̄ random subspace bases
o
T
Cluster by projection
ck ← x ∈ X : ∀j Uk x 2 ≥ UjT x 2 for k = 1, . . . , K̄
for t = 1, . . . , T (in sequence) do
Uk ←nPCA ck , d¯ for k = 1, . . . , K̄
Estimate subspaces
o

ck ← x ∈ X : ∀j UkT x 2 ≥ UjT x
end for
C (b) ← {c1 , . . . , cK̄ }
end for 
Ai,j ← B1 b : xi , xj are co-clustered in C (b)
Ā ← T HRESH(A, q)
C ← S PECTRAL C LUSTERING(Ā, K)

2

for k = 1, . . . , K̄

Cluster by projection

for i, j = 1, . . . , N

Form affinity matrix
Keep top q entries per row/column
Final Clustering

clustered together, we add one to the (i, j)th entry of the co-association matrix. We then threshold the co-association matrix as
in [18] by taking the top q values from each row/column. Once this thresholded co-association matrix is formed, cluster labels
are obtained using spectral clustering. Pseudocode for EKSS is given in Alg. 1, where T HRESH sets all but the top q entries
in each row/column to zero as in [18] (pseudocode for this procedure is given in Appendix C) and S PECTRAL C LUSTERING
[34] clusters the data points based on the co-association matrix A. Note that the number of candidates K̄ and candidate
dimension d¯ need not match the number K and dimension of the true underlying subspaces. Fig. 1 shows the progression of
the co-association matrix as B = 1, 5, 50 base clusterings are used, in the case of noiseless data from K = 4 subspaces of
dimension d = 10 in ambient space of dimension D = 100 using K̄ = 4 candidates of dimension d¯ = 10.
A. Recovery Guarantees
Recovery guarantees for KSS are still absent despite nearly twenty years of use since its introduction. Intelligent initialization
methods based on probabilistic farthest insertion are provided in [20], [22], but these still lack any theoretical guarantees. In
this section, we provide a first step toward understanding the performance of KSS, as well as recovery guarantees for the
subspace clustering problem. We show that by combining the clusterings that result from many random initializations of
subspace candidates, the entries of the resulting affinity matrix converge to a monotonically increasing function of the absolute
value of inner product between points. A corollary of this fact is that a simplified version of EKSS exhibits all the recovery
guarantees of TSC [18]. To the best of our knowledge, our work is the first to provide any theoretical guarantees for the KSS
algorithm as well as the first characterization of the co-association matrix in the context of consensus clustering.
Due to its alternating nature, analyzing multiple iterations of the KSS algorithm remains challenging. Instead, we analyze
the first iteration of KSS (T = 0 in Alg. 1), in which random candidates are drawn and points are clustered based on their
nearest candidate. Further, we restrict ourselves to the case where the number of candidates (not the number of subspaces)
is K̄ = 2 and the candidate dimension (not the true subspace dimension) is d¯ = 1. Finally, for the purposes of analysis, we
replace the unit norm candidates in Step 4 with Gaussian random vectors, noting that the two are nearly equivalent in high
dimensions due to concentration of the norm [35, Thm. 3.1.1]. We refer to EKSS with this choice of parameters as EKSS-0
and include explicit pseudocode in Appendix A. Remarkably, we show that combining the results from many random instances
of this naïve algorithm leads to the same recovery guarantees as TSC, which are in turn comparable to those for SSC. While
we do not analyze the case where multiple KSS iterations are performed, these iterations are guaranteed not to increase the
KSS cost function, and in practice, we find that running KSS to convergence only improves clustering performance.
We now state our main result, which guarantees that EKSS-0 described in the preceding paragraph is able to cluster the
points in X exactly under given conditions on the maximum affinity between subspaces and the number of points per subspace.
This result matches that of TSC [18, Thm. 2] exactly, and our proof leverages the proof of that used in [18] by applying
Lemma 1 below. Our guarantees depend on the affinity between two subspaces, defined as [18], [36]
aff(Sk , Sl ) = √

1
UkT Ul
dk ∧ dl

F

,

(2)

where Sk and Sl are dk - and dl -dimensional subspaces with orthonormal bases Uk and Ul . Note that aff(Sk , Sl ) is a measure
of how close two subspaces are in terms of their principal angles and takes the value 1 if two subspaces are equivalent and 0
if they are orthogonal.

4

Fig. 1: Co-association matrix of EKSS for B = 1, 5, 50 base clusterings. Data generation parameters are D = 100, d = 10,
K = 4, N = 400, and the data is noise-free; the algorithm uses K̄ = 4 candidate subspaces of dimension d¯ = 10. Resulting
clustering errors are 54%, 25%, and 0%.
Theorem 1. Let Sk , k = 1, . . . , K be subspaces of dimension d1 , . . . , dK in RD . Let the points in Xk be a set of Nk points
drawn P
uniformly from the unit sphere in subspace k, i.e., from the set {x ∈ Sk : kxk = 1}. Let X = X1 ∪ · · · ∪ XK and
d−1
, and
N =
k Nk . Let q ∈ [c1 log Nmax , Nmin /6], where Nmin = mink {Nk }, Nmax = maxk {Nk }, c1 = 18(12π)
d = max{d1 , . . . , dK }. If
1
max aff(Sk , Sl ) ≤
,
k,l:k6=l
15 log N
then in the limit
 the correct clustering of X with probability at least
PKas B → ∞, EKSS-0 delivers
1 − 10/N − k=1 Nk e−c(Nk −1) + 2Nk−2 , where c > 0 is a numerical constant.

Proof of Theorem 1. The proof hinges on the following lemma, which states that in the case where T = 0, d¯ = 1, and K̄ = 2,
points xi and xj are clustered together with probability that increases monotonically with xTi xj .

Lemma 1. The probability that two points xi , xj ∈ X are clustered together by one base clustering of EKSS-0 (i.e., EKSS-0
with B = 1) is an increasing function of xTi xj .
The proof of Lemma 1 is given in Appendix A. By the Law of Large Numbers, when B → ∞, each entry Ai,j of the
affinity matrix A approaches the probability analyzed in Lemma 1, and hence is also an increasing function of xTi xj . Next,
note that the result of [18, Thm. 2] depends only on the relative order of xTi xj (namely, through [18, Lemma 1] and [18,
Lemma 2]). By Lemma 1, the order of entries in A is the same as in TSC, and so (as B → ∞) the thresholded affinity matrix
Ā of EKSS-0 has the same connectivity as that formed by TSC [18]. The result of the theorem follows directly by the proof
of [18, Thm. 2].
Thm. 1 states that perfect clustering of the data is guaranteed even in the case of intersecting subspaces, as long as the
subspaces are not too close in all directions. The clustering condition for Thm. 1 above is the same as that for SSC in [12] up
to constants and log factors. Along with the above result, all recovery guarantees of TSC follow from Lemma 1, indicating
that EKSS-0 results in no false connections under noisy data, missing data, and outliers. For a discussion of these guarantees
and their relation to those for SSC and other algorithms, see [18, Sec. VII]. The inverse dependence on log N implies that
the subspace affinity must shrink as N grows. On one hand, this is intuitive because with many points per subspace, it is
likely that some points will be close to the intersection of two subspaces and potentially be misclustered. On the other hand,
more points allows for a better chance that the nearest point by inner product is within the same subspace. Indeed, in all the
empirical results we see that both EKSS and TSC perform better with larger N . Finally, we note that while the above analysis
holds only for the case of T = 0, letting T > 0 is guaranteed not to increase the KSS cost function [6]. The extension of Thm.
1 to the case where T > 0 is an important topic of our ongoing research.
B. Implementation Details
In this section, we explain a few relevant implementation details, including a warm start extension of EKSS that we will
show outperforms state-of-the-art methods on several benchmark datasets.
A natural heuristic to improve the clustering performance of EKSS is to add larger values to the affinity matrix for base
clusterings in which the clustering is believed to be more accurate, and smaller values in the case where the clustering is
believed to be more inaccurate. Here, we briefly describe
one such approach. Note that Step 12 in EKSS is equivalent

PB
(b)
to setting A ← B1 b=1 A(b) φ(b), where Ai,j := 1 xi , xj are clustered together in C (b) and φ(b) = 1. One measure
of clustering accuracy is the cost function of KSS with the clusters and subspace bases set as the clustering output. Let

5

EKSS-0

0

EKSS

TSC

SSC

Nk

0.6

200
0.5

400
0.4

0

20

40

60

0

20

d

40

60

0

20

d

40

60

0

20

d

40

60

d

0.3

20
0.2

Nk

40
60

0.1

80
100
0

0.2

0.4

0.6

0.8 0

0.2

θ

0.4

0.6

0.8 0

0.2

θ

0.4

0.6

0.8 0

θ

0.2

0.4

0.6

0.8

0

θ

Fig. 2: Clustering error for proposed and state-of-the-art subspace clustering algorithms as a function of problem parameters
Nk , number of points per subspace, and true subspace dimension d or angle between subspaces θ. Fixed problem parameters
are D = 100, K = 3.
o
o
n
n
(b)
(b)
(b)
(b)
C (b) = c1 , . . . , cK , and let U (b) = U1 , . . . , UK denote the set of subspace bases estimated by performing PCA on
the points in the corresponding clusters. The clustering confidence can then be measured as
φ(b) = 1 −

K
X

X

k=1 i:xi ∈c(b)

(b)

(b) T

xi − Uk Uk

2

xi
2

2

/ kXkF ,

(3)

k

a value between 0 and 1 that decreases as the KSS cost increases. We employ this value of φ(b) in all experiments on real
data.
1) Warm-Start EKSS: It is well-known that the performance of alternating methods in optimization depends on the initialization of the problem parameters [37], [38]. For this reason, we propose a warm-start method to further improve robustness to
outliers and noise. We first run EKSS with a small number of base clusterings (typically 10). Then, using the estimated labels
obtained from this run, we form a set of initial candidate subspace bases by performing PCA on the points in each cluster.
These candidate bases are then used to initialize KSS in place of random candidates for each b = 1, . . . , B in EKSS. We refer
to this variant as EKSS-WS (warm-start), and pseudocode for this algorithm is given in Appendix C.
2) Parameter Selection: In all experiments using EKSS, we take K̄ = K and choose d¯ as the best approximation of the
true subspace dimension. We assume in this work that a good approximating dimension for the underlying subspace is known,
which is reasonable in several practical applications. For example, images of a Lambertian object under varying illumination
are known to lie near a subspace with d = 9 [1] and moving objects in video are known to lie near an affine subspace with
¯ or methods such as those
d = 3 [39]. In the case of unknown subspace dimensions, one could use EKSS with increasing d,
proposed in [8] could be employed.
Rather than choosing T explicitly in Alg. 1, we run KSS to convergence. The EKSS algorithm then relies on the appropriate
choice of the number of base clusterings B and the thresholding parameter q. In general, B may be chosen as large as
computation time allows. In our experiments on real data, we choose B = 1000. The thresholding parameter q can be chosen
according to data-driven techniques as in [40], or following the choice in [18]. In our experiments on real data, we select the
best q in a large range of values for each EKSS and TSC to provide a fair comparison. For the warm-start run of EKSS-WS,
both B and q should be small (we choose B = 10 and q = 3). For comparison, TSC requires the choice of q, and SSC [10] and
its variants [16], [17] all require two parameters to be selected. Finally, we use the implementation of S PECTRAL C LUSTERING
from [10].
IV. E XPERIMENTAL R ESULTS
In this section, we demonstrate the performance in terms of clustering error (defined in Appendix C) of EKSS on both
synthetic and real datasets. We first show the performance of our algorithm as a function of the relevant problem parameters
and verify that EKSS-0 exhibits the same empirical performance as TSC. We also show that EKSS can recover subspaces that
either have large intersection or are extremely close. We then demonstrate on real datasets that EKSS not only improves over
previous iterative methods, but that the warm-start variant of EKSS surpasses state-of-the-art results in many cases.

misclassification %

6

0.6

EKSS-0
TSC
EKSS
SSC

0.5
0.4
0.3
0.2
0.1
0.2

0.4

0.6

0.8

θ
Fig. 3: Clustering error as a function of subspace angles with noisy data. Problem parameters are D = 100, d = 10, K = 3,
Nk = 500, σ 2 = 0.05.
A. Synthetic Data
For all experiments in this section, we take q = max(3, ⌈Nk /20⌉) for EKSS-0 and TSC and q = max(3, ⌈Nk /6⌉) for
EKSS, where ⌈c⌉ denotes the largest integer greater than or equal to c. We set B = 10, 000 for EKSS-0 and EKSS. To
validate our theoretical results, we draw Gaussian candidates, rather than orthonormal bases, for EKSS-0. When the angles
between subspaces are not explicitly specified, it is assumed that the subspaces are drawn uniformly at random from the set
of all d-dimensional subspaces of RD . For all experiments, we draw points uniformly at random from the unit sphere in
the corresponding subspace and show the mean error over 100 random problem instances. We use the code provided by the
authors for TSC and SSC. We employ the ADMM implementation of SSC and choose the parameters that result in the best
performance in each scenario.
We explore the influence of some relevant problem parameters on the EKSS algorithm in Fig. 2. We take the ambient
dimension to be D = 100, the number of subspaces to be K = 3, and assume the data to be noiseless.
We first explore the dependence on subspace dimension and the number of points per subspace. The top row of Fig. 2 shows
the misclassification rate as the number of points per subspace ranges from 10 − 500 and the subspace dimension ranges from
1 − 75. When 2d > D (d = 51 in this case), pairs of subspaces necessarily have intersection, and the intersection dimension
grows with d. First, the figures demonstrate that EKSS-0 achieves roughly the same performance as TSC, resulting in correct
clustering even in the case of subspaces with large intersection. Second, we see that EKSS can correctly cluster for subspace
dimensions larger than that of TSC as long as there are sufficiently many points per subspace. For large subspace dimensions
with a moderate number of points per subspace, SSC achieves the best performance.
We next explore the clustering performance as a function of the distance between subspaces, as shown in the second row
of Fig. 2. We set the subspace dimension to d = 10 and generate K = 3 subspaces such that all principal angles are θ, for
20 values in the range [0.001, 0.8]. Most strikingly, EKSS is able to resolve subspaces with even the smallest separation. This
stands in contrast to TSC, which fails in this regime because when the subspaces are extremely close, the inner products
between points on different subspaces can be nearly as large as those within the same subspace. Similarly, in the case of SSC,
points on a different subspace can be used to regress any given point without any added cost, and so it fails at very small
subspace angles. However, as long as there is still some separation between subspaces, EKSS is able to correctly cluster all
points. While the theory presented here does not capture this phenomenon, recovery guarantees that take into account multiple
iterations of KSS are an important topic for future work.
As a final comparison, we show the clustering performance with noisy data. Fig. 3 shows the clustering error as a function
of the angle between subspaces for the case of K = 3 subspaces of dimension d = 10, with Nk = 500 points corrupted by
zero-mean Gaussian noise with covariance 0.05ID . The figure shows again that EKSS-0 and TSC obtain similar performance,
and more importantly that EKSS is more robust to small subspace angles than SSC, even in the case of noisy data.
B. Real Data
In this section, we show that EKSS achieves competitive performance on a variety of real datasets commonly used as
benchmarks in the subspace clustering literature. We consider the Hopkins-155 dataset [2], the cropped Extended Yale Face
Database B [4], [42], COIL-20 [43] and COIL-100 [44] object databases, the USPS dataset provided by [45], and 10,000 digits
of the MNIST handwritten digit database [5], where we obtain features using a scattering network [46] as in [17]. Descriptions
of these datasets and the relevant problem parameters are included in Appendix C. For the Hopkins-155 database, we report
both the mean and median misclassification rates, as is common in the literature [10], [22]. We compare the performance
of EKSS to several benchmark algorithms: KSS [6], Median K-Flats (MKF) [20], TSC [18], SSC-OMP [16], Elastic Net

7

Algorithm
EKSS
EKSS-WS
KSS
MKF
TSC
SSC-ADMM
SSC-OMP
EnSC
OLRSC

Hopkins
5.84/0.32
3.82/0.00
7.00/0.79
5.22/0.21
27.19/27.27
2.18/0.00
35.77/36.65
24.96/24.21
20.70/18.12

Yale B
22.33
16.12
75.70
47.70
20.81
31.03
22.41
21.26
55.14

COIL-20
24.79
7.01
65.56
54.79
15.35
22.43
46.67
15.14
35.42

COIL-100
36.36
28.03
74.53
66.49
39.03
44.06
62.12
28.75
50.79

USPS
33.21
26.09
51.30
28.62
33.46
56.61
78.43
33.66
29.71

MNIST-10k
26.18
17.54
48.15
47.14
17.17
19.17
19.47
17.97
20.50

TABLE I: Clustering error of subspace clustering algorithms for a variety of benchmark datasets. Hopkins-155 performance
is (mean/median). The lowest two clustering errors are given in bold.
Subspace Clustering (EnSC) [17], and Online Low-Rank Subspace Clustering (OLRSC) [15]. For EKSS we use B = 1000
base clusterings. For all others but KSS, we use the code provided by the authors and use the recommended parameters where
available and otherwise use parameters that result in the best performance. For a fair comparison to KSS and MKF, we run
1000 trials of each and use the clustering result that achieves the lowest KSS cost. We refer to the warm-start variant of EKSS
as EKSS-WS. Further implementation details, including parameter selection and data preprocessing, can be found in Appendix
C.
The clustering error for all datasets and algorithms is shown in Table I, with the lowest two errors given in bold. First,
note that EKSS outperforms KSS in all cases, and typically by a very large margin. This result emphasizes the importance
of leveraging all clustering information from the B base clusterings, as opposed to simply choosing the best single clustering.
Next, the results show that EKSS-WS is among the top two performers in all datasets considered. Although code for the method
from [22] was unavailable, EKSS-WS achieves similar performance to the reported misclassification rate on the Hopkins-155
dataset. We also observe that scalable algorithms such as SSC-OMP and EnSC perform poorly on the Hopkins dataset, likely
due to the small number of points, whereas EKSS works well under both small and large N . Most striking are the resulting
misclassification rates on the Yale B and COIL-20 datasets, for which EKSS-WS significantly outperforms the best existing
algorithm. Interestingly, TSC achieves the best performance on the MNIST-10k dataset, whereas EnSC achieves much better
performance on the full 70,000-digit database as reported in [17]. Due to memory constraints we were unable to compare
performance on the full MNIST database for most algorithms including EKSS. Implementing a memory-efficient version of
EKSS is an important topic of future work.
V. C ONCLUSION
In this work, we presented a first step toward a theoretical understanding of the KSS algorithm by analyzing the effect of
combining multiple clusterings using the evidence accumulation clustering framework. We showed that with a given choice of
parameters, our algorithm can provably cluster data from a union of subspaces under the same conditions as existing algorithms.
We demonstrated the efficacy of our approach on both synthetic and real data, and showed that a warm-start variant of our
method achieves excellent performance on several real datasets.
While the theoretical guarantees presented here match existing guarantees in the literature, our experiments on synthetic data
indicate that the iterative approach of KSS provides a major improvement in robustness to small angles between subspaces.
Further, while our results hold only for the case of two 1-dimensional candidates, we observed a performance improvement
in the case where more than two d-dimensional candidates are used. Extending our analysis to the general case of Alg. 1
(e.g., T > 0, d¯ > 1, and K̄ > 2) is an important next step. Finally, while EKSS-WS with the given parameter choices
achieves excellent empirical performance, a deeper understanding of appropriate parameter selection for this method could
lead to improved performance and robustness across different datasets.

8

Algorithm 2 EKSS-0
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

Input: X = {x1 , x2 , . . . , xN } ⊂ RD : data, K: number of output clusters, q ∈ N: threshold parameter, B: number of base
clusterings
Output: C = {c1 , . . . , cK }: clusters of X
for b = 1, . . . , B (in parallel)
do

1
u1 , u2 ∼ N 0, D
Draw two random candidates
ID
ck ← x ∈ X : uTk x ≥ uTl x for k, l = 1, 2
Cluster by inner product
C (b) ← {c1 , c2 }
end for 
Ai,j ← B1 b : xi , xj are clustered together in C (b) for i, j = 1, . . . , N
Form affinity matrix
Ā ← T HRESH(A, q)
Threshold
C ← S PECTRAL C LUSTERING(Ā, K)
Final Clustering
A PPENDIX A
P ROOF OF L EMMA 1

In this section, we prove Lemma 1 of Section III-A, which allows us to leverage the connectivity results for TSC [18] in
Theorem 1. For convenience, we include pseudocode for the explicit EKSS-0 algorithm in Alg. 2 and restate the lemma below.
Lemma 1. The probability that two points xi , xj ∈ X are clustered together by one base clustering of EKSS-0 (i.e., EKSS-0
with B = 1) is an increasing function of xTi xj .
1
Proof. Let u, v ∼ N (0, D
ID ) be two one-dimensional Gaussian candidates in EKSS-0. Then u and v are orthogonally
1
ID ) for any orthogonal matrix Q. Furthermore, x and y cluster together if and only if x and
invariant, i.e., Qu, Qv ∼ N (0, D
−y cluster together. As a result, we can consider x = [1 0 · · · 0]T and y = [cos θ sin θ 0 · · · 0]T where 0 < θ < π/2 without
loss of generality. The points x and y are clustered together when

(|u1 | > |v1 | and |u1 cos θ + u2 sin θ| > |v1 cos θ + v2 sin θ|)

or
(|u1 | < |v1 | and |u1 cos θ + u2 sin θ| < |v1 cos θ + v2 sin θ|).

(4)
(5)

Note that (4) and (5) are disjoint events and occur with equal probability since u and v are identically distributed. The remainder
of the proof is dedicated to showing that the conditional probability of (4) given u1 and v1 is a decreasing function of θ when
|u1 | > |v1 |. From this fact, it follows that the probability of (4) is a decreasing function of θ by the law of total probability
(taken over u1 and v1 ). Lemma 1 follows then because (5) has equal probability and θ = arccos(|xT y|) is a decreasing function
of |xT y|.
Observe that
h
i
|u1 | > |v1 | ⇐⇒ (u1 + v1 > 0 and u1 − v1 > 0) or (u1 + v1 < 0 and u1 − v1 < 0)
(6)
|
|
{z
}
{z
}
i.e., u1 >|v1 |

i.e., u1 <−|v1 |

and likewise
|u1 cos θ + u2 sin θ| > |v1 cos θ + v2 sin θ|

(7)

or (u2 + v2 < −(u1 + v1 ) cot θ and u2 − v2 < −(u1 − v1 ) cot θ).

(9)

⇐⇒
(u2 + v2 > −(u1 + v1 ) cot θ and u2 − v2 > −(u1 − v1 ) cot θ)

(8)

For convenience, let s1 = u1 + v1 , d1 = u1 − v1 , s2 = u2 + v2 and d2 = u2 − v2 . The random variables s2 and d2 are
i.i.d. Gaussian random variables because the vector [s2 d2 ]T is a scaled rotation of [u2 v2 ]T and u2 and v2 are i.i.d. Gaussian
random variables. From (6) and (7), it follows that when |u1 | > |v1 |, either s1 , d1 > 0 or s1 , d1 < 0 and the conditional
probability of (4) given u1 and v1 is
ρ(θ) = P {|u1 | > |v1 | and |u1 cos θ + u2 sin θ| > |v1 cos θ + v2 sin θ| : u1 , v1 }

= P {|u1 cos θ + u2 sin θ| > |v1 cos θ + v2 sin θ| : u1 , v1 }
= P {(s2 > −s1 cot θ and d2 > −d1 cot θ) or (s2 < −s1 cot θ and d2 < −d1 cot θ) : s1 , d1 }
= P {s2 > −s1 cot θ : s1 } P {d2 > −d1 cot θ : d1 } + P {s2 < −s1 cot θ : s1 } ×
P {d2 < −d1 cot θ : d1 }
= (1 − F (−s1 cot θ))(1 − F (−d1 cot θ)) + F (−s1 cot θ)F (−d1 cot θ)

(10)

9

Rx
where F (x) = −∞ f (τ )dτ is the CDF for the i.i.d. Gaussian random variables u2 and v2 with density f (x).
Differentiating (10) with respect to θ and factoring yields



2 
ρ′ (θ) = − csc
1 cot θ) d1 (1 − 2F (−s1 cot θ)) + f (−s1 cot θ) s1 (1 − 2F (−d1 cot θ))
| {z θ} f| (−d{z
}|
{z
} |
{z
}|
{z
}
>0

>0

=:δ1

>0

=:δ2

Recall that either s1 , d1 > 0 or s1 , d1 < 0 . We consider each case:
1) If s1 , d1 > 0 then F (−s1 cot θ), F (−d1 cot θ) ≤ 1/2 with equality only when θ = π/2. As a result δ1 , δ2 ≥ 0 with
equality only when θ = π/2.
2) If s1 , d1 < 0 then F (−s1 cot θ), F (−d1 cot θ) ≥ 1/2 with equality only when θ = π/2. Once again δ1 , δ2 ≥ 0 with
equality only when θ = π/2.
Thus it follows that ρ′ (θ) ≤ 0 with equality only when θ = π/2 and so the conditional probability ρ(θ) of (4) given u1 and
v1 is a decreasing function of θ when |u1 | > |v1 |.
A PPENDIX B
N ON -G LOBAL C ONVERGENCE OF K - SUBSPACES
In this section, we prove the claim that there is a set of initializations of nonzero measure that will necessarily lead the
K-subspaces (KSS) algorithm to a solution that is not a global minimizer for the simple case of two one-dimensional subspaces
of R2 .
Proposition 1. Consider two one-dimensional subspaces S1 , S2 ⊂ R2 having angle between them θ ∈ (0, π/2). The set of
initializations such that KSS converges to a clustering that is not a global optimum has nonzero measure.
Proof. Let u1 , u2 be the true subspace bases, and let v1 , v2 be the candidate bases initialized uniformly at random from the unit
sphere. Let θu,v denote the angle between vectors u and v, i.e., θu,v = cos−1 uT v , where by symmetry we only consider angles

T

T
at most π/2. By rotation invariance of the candidate subspaces, we assume that u1 = 1 0 and u2 = cos(θ) sin(θ)
without loss of generality. Consider the case where θu1 ,v1 > θ and θu1 ,v2 > θ, and note that each event occurs independently
with probability π/2 − θ. Next, note that θu2 ,v1 < θu2 ,v2 implies θu1 ,v1 < θu1 ,v2 , in which case all points are assigned to v1 .
Similarly, θu2 ,v2 < θu2 ,v1 implies θu1 ,v2 < θu1 ,v1 , in which case all points are assigned to v2 . Thus, all points are clustered
to the same candidate subspace as long as both θu1 ,v1 > θ and θu1 ,v2 > θ, which occurs with probability (π/2 − θ)2 . Under
this event, KSS converges after the first iteration, as the subspace corresponding one candidate is null. Hence, the set of
initializations such that KSS converges to a local and not global optimum has measure at least (π/2 − θ)2 .
A PPENDIX C
I MPLEMENTATION D ETAILS
In this section, we include implementation details beyond those included in Section III-B. We first provide pseudocode for
the T HRESH and EKSS-WS algorithms. We then describe all preprocessing steps and parameters used for our experiments
on real data.
A. Clustering Error
The clustering error, which is the metric used for all experimental results, is computed by matching the true labels and the
labels output by a given clustering algorithm,


X
1
true 
err = 100 1 − max
Qout
,
π(i)j Qij
π N
i,j
where π is a permutation of the cluster labels, and Qout and Qtrue are the output and ground-truth labelings of the data,
respectively, where the (i, j)th entry is one if point j belongs to cluster i and is zero otherwise.
B. Pseudocode
In Algorithm 3 is the pseudocode for the T HRESH routine used in the EKSS algorithm, which results in the same connectivity
as thresholding in TSC [18].

10

Algorithm 3 A FFINITY T HRESHOLD (T HRESH )
1:
2:
3:
4:
5:
6:
7:

Input: A ∈ [0, 1]N ×N : affinity matrix, q: threshold parameter
Output: Ā ∈ [0, 1]N ×N : thresholded affinity matrix
for i = 1, . . . , N do
row
Zi,:
← Ai,: with the smallest N − q entries set to zero.
col
Z:,i
← A:,i with the smallest N − q entries set to zero.
end for

Ā ← 21 Z row + Z col

Threshold rows
Threshold columns
Average

Algorithm 4 EKSS WARM -S TART (EKSS-WS)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

¯ candidate dimension, K: number of
Input: X = {x1 , x2 , . . . , xN } ⊂ RD : data, K̄: number of candidate subspaces, d:
output clusters, q1 , q2 : threshold parameters, B1 , B2 : number of base clusterings, T : number of KSS iterations
Output: C = {c1 , . . . , cK }: clusters of X
for b = 1, . . . , B1 (in parallel) do

¯ K̄, q2 , B2 , T
{c1 , . . . , cK̄ } ← EKSS X , K̄, d,
for t = 1, . . . , T (in sequence) do
Uk ←nPCA ck , d¯ for k = 1, . . . , K̄
Estimate subspaces
o
ck ← x ∈ X : ∀j UkT x 2 ≥ UjT x 2 for k = 1, . . . , K̄
end for
C (b) ← {c1 , . . . , cK̄ }
end for

Ai,j ← B11 b : xi , xj are clustered together in C (b) for i, j = 1, . . . , N
Ā ← T HRESH(A, q1 )
C ← S PECTRAL C LUSTERING(Ā, K)

Cluster by projection

Form affinity matrix
Keep top q1 entries per row/column
Final Clustering

We also give in Algorithm 4 the pseudocode for EKSS-WS, which calls the EKSS algorithm given in Algorithm 1. Recall
that the algorithm proceeds by first running EKSS for a small number of base clusterings (typically B2 ≈ 10). The output
clustering is then used to initialize KSS for each of the B1 base clusterings of the main loop.
C. Experiments on Real Data
In this section, we describe the real datasets used in our experiments, as well as any preprocessing steps and the parameters
selected for all algorithms. All datasets are normalized so that each column lies on the unit sphere in the corresponding ambient
dimension, as is common in the literature [12], [18], [22]. Table II gives a summary of all datasets considered.
The Hopkins-155 dataset [2] consists of 155 motion sequences with K = 2 in 120 of sequences and K = 3 in the remaining
35. In each sequence, objects moving along different trajectories each lie near their own affine subspace of dimension at most
3. We perform no preprocessing steps on this dataset.
The Extended Yale Face Database B [4], [42] consists of 64 images of each of 38 different subjects under a variety of
lighting conditions. Each image is of nominal size 192 × 168 and is known to lie near a 9-dimensional subspace [1]. We
downsample so that each image is of size 48 × 42, as in [10]. For EKSS, EKSS-WS, KSS, MKF, TSC, and OLRSC, we
perform an initial whitening as in [23], [18] by removing the first two singular components of the dataset and then project the
data onto its first 500 principal components to reduce the computational complexity of these methods. Whitening resulted in
worse performance for all other algorithms, so we omitted this step.
The COIL-20 [43] and COIL-100 [44] datasets consist of 72 images of 20 and 100 distinct objects (respectively) under a
variety of rotations. All images are of size 32 × 32. On both datasets, we whiten by removing the first singular component
when it improves algorithm performance.
The USPS dataset provided by [45] contains 9,298 total handwritten digits of size 16×16 with roughly even label distribution.
No preprocessing is performed on this dataset.
The MNIST dataset [5] contains a total of 70,000 handwritten digits, of which we consider only the 10,000 “test” images.
The images have nominal size 28 × 28, and we use the output of a scattering convolutional network [46] of size 3,472 and
then project onto the first 500 principal components as in [17].
The parameters used for all experiments are shown in Table III. We use the recommended parameters where available and
choose the parameters that result in the best performance in all other cases. For OLRSC [15], we use the recommended
parameters, set the basis dimension as K ∗ d, and report the minimum error between the standard and fully online pipelines,
indicated by ‘S’ and ‘F’ in the table.

11

Dataset
Hopkins-155
Yale
COIL-20
COIL-100
USPS
MNIST-10k

N
39-556
2432
1440
7200
9298
10000

K
2-3
38
20
100
10
10

D
30-200
2016
1024
1024
256
500

d
3
9
9
9
15
3

TABLE II: Datasets used for experiments with relevant parameters; N : total number of samples, K: number of clusters, D:
ambient dimension, d: estimated subspace dimension.
Algorithm
EKSS
EKSS-WS
TSC
SSC-ADMM
SSC-OMP
EnSC
OLRSC

Hopkins
B = 1000, q = 15
B1 = 1000, q1 = 15
B2 = 10, q2 = 3
q=3
ρ = 0.7, α = 800
ε = 2−52 , kmax = 3
λ = 0.1, α = 3
F

Yale
B = 1000, q = 5
B1 = 1000, q1 = 19
B2 = 10, q2 = 3
q=3
ρ = 1, α = 20
ε = 2−52 , kmax = 5
λ = 0.95, α = 3
S

COIL-20
B = 1000, q = 35
B1 = 1000, q1 = 50
B2 = 10, q2 = 3
q=8
ρ = 1, α = 20
ε = 2−52 , kmax = 5
λ = 0.95, α = 3
F

COIL-100
B = 1000, q = 11
B1 = 1000, q1 = 60
B2 = 10, q2 = 3
q=8
ρ = 1, α = 20
ε = 2−52 , kmax = 5
λ = 0.95, α = 3
F

USPS
B = 1000, q = 7
B1 = 1000, q1 = 500
B2 = 10, q2 = 3
q=5
ρ = 1, α = 20
ε = 2−52 , kmax = 5
λ = 0.95, α = 50
F

MNIST-10k
B = 1000, q = 9
B1 = 1000, q1 = 8
B2 = 10, q2 = 3
q=9
ρ = 1, α = 20
ε = 2−52 , kmax = 12
λ = 0.95, α = 3
F

TABLE III: Parameters used in experiments on real datasets for all algorithms considered.

R EFERENCES
[1] R. Basri and D. Jacobs, “Lambertian reflectance and linear subspaces,” IEEE TPAMI, vol. 25, no. 2, pp. 218–233, February 2003.
[2] R. Tron and R. Vidal, “A benchmark for the comparison of 3-D motion segmentation algorithms,” in IEEE Int. Conf. on Comp. Vision and Pattern
Recog., 2011.
[3] R. Vidal, S. S. Sastry, and Y. Ma, Generalized Principal Component Analysis. Springer-Verlag, 2016.
[4] A. Georghiades, P. Belhumeur, and D. Kriegman, “From few to many: Illumination cone models for face recognition under variable lighting and pose,”
IEEE Trans. Pattern Anal. Mach. Intelligence, vol. 23, no. 6, pp. 643–660, 2001.
[5] Y. LeCun, C. Cortes, and C. J. C. Burges, “The MNIST database of handwritten digits,” 2016. [Online]. Available: yann.lecun.com/exdb/mnist
[6] P. S. Bradley and O. L. Mangasarian, “k-Plane clustering,” Journal of Global Optimization, vol. 16, pp. 23–32, 2000.
[7] P. Tseng, “Nearest q-flat to m points,” Journal of Optimization Theory and Applications, vol. 105, no. 1, pp. 249–252, 2000.
[8] P. K. Agarwal and N. H. Mustafa, “K-means projective clustering,” in Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on
Principles of database systems. ACM, 2004, pp. 155–165.
[9] A. L. Fred and A. K. Jain, “Combining multiple clusterings using evidence accumulation,” IEEE transactions on pattern analysis and machine intelligence,
vol. 27, no. 6, pp. 835–850, 2005.
[10] E. Elhamifar and R. Vidal, “Sparse subspace clustering: Algorithm, theory, and applications,” IEEE Trans. on Pattern Analysis and Machine Intelligence,
vol. 35, pp. 2765–2781, Nov. 2013.
[11] G. Liu, Z. Lin, and Y. Yu, “Robust subspace segmentation by low-rank representation,” in Proceedings of the 27th international conference on machine
learning (ICML-10), 2010, pp. 663–670.
[12] M. Soltanolkotabi and E. J. Candes, “A Geometric Analysis of Subspace Clustering with Outliers,” The Annals of Statistics, vol. 40, no. 4, pp. 2195–2238,
2012.
[13] C.-Y. Lu, H. Min, Z.-Q. Zhao, L. Zhu, D.-S. Huang, and S. Yan, “Robust and efficient subspace segmentation via least squares regression,” Computer
Vision–ECCV 2012, pp. 347–360, 2012.
[14] R. Vidal and P. Favaro, “Low rank subspace clustering (lrsc),” Pattern Recognition Letters, vol. 43, pp. 47–61, 2014.
[15] J. Shen, P. Li, and H. Xu, “Online low-rank subspace clustering by basis dictionary pursuit,” in Proc. International Conference on Machine Learning,
2016.
[16] C. You, D. P. Robinson, and R. Vidal, “Scalable sparse subspace clustering by orthogonal matching pursuit,” in Proc. IEEE Conf. on Computer Vision
and Pattern Recognition, 2015.
[17] C. You, C.-G. Li, D. P. Robinson, and R. Vidal, “Oracle based active set algorithm for scalable elastic net subspace clustering,” arXiv, vol. 1605.02633v1,
2016.
[18] R. Heckel and H. Bölcskei, “Robust subspace clustering via thresholding,” IEEE Trans. Inf. Theory, vol. 24, no. 11, pp. 6320–6342, 2015.
[19] D. Park, C. Caramanis, and S. Sanghavi, “Greedy subspace clustering,” in Advances in Neural Information Processing Systems, 2014, pp. 2753–2761.
[20] T. Zhang, A. Szlam, and G. Lerman, “Median k-flats for hybrid linear modeling with many outliers,” in Computer Vision Workshops (ICCV Workshops),
2009 IEEE 12th International Conference on. IEEE, 2009, pp. 234–241.
[21] L. Balzano, A. Szlam, B. Recht, and R. Nowak, “K-Subspaces with missing data,” in Statistical Signal Processing Workshop (SSP), 2012 IEEE. IEEE,
2012, pp. 612–615.
[22] J. He, Y. Zhang, J. Wang, N. Zeng, and H. Hao, “Robust k-subspaces recovery with combinatorial initialization,” in Big Data (Big Data), 2016 IEEE
International Conference on. IEEE, 2016, pp. 3573–3582.
[23] T. Zhang, A. Szlam, Y. Wang, and G. Lerman, “Hybrid linear modeling via local best-fit flats,” International Journal of Computer Vision, vol. 100, pp.
217–240, 2012.
[24] J. Ghosh and A. Acharya, “Cluster ensembles,” Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 1, no. 4, pp. 305–315,
2011.
[25] F. Leisch, “Bagged clustering,” WU Vienna University of Economics and Business, Tech. Rep., 1999.
[26] B. Minaei-Bidgoli, A. Topchy, and W. F. Punch, “Ensembles of partitions via data resampling,” in Information Technology: Coding and Computing,
2004. Proceedings. ITCC 2004. International Conference on, vol. 2. IEEE, 2004, pp. 188–192.
[27] K. Tumer and A. K. Agogino, “Ensemble clustering with voting active clusters,” Pattern Recognition Letters, vol. 29, no. 14, pp. 1947–1953, 2008.
[28] A. Topchy, A. K. Jain, and W. Punch, “Clustering ensembles: Models of consensus and weak partitions,” IEEE Transactions on pattern analysis and
machine intelligence, vol. 27, no. 12, pp. 1866–1881, 2005.
[29] A. Fred and A. K. Jain, “Evidence accumulation clustering based on the k-means algorithm,” in Joint IAPR International Workshops on Statistical
Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). Springer, 2002, pp. 442–451.
[30] A. L. Fred and A. K. Jain, “Data clustering using evidence accumulation,” in Pattern Recognition, 2002. Proceedings. 16th International Conference on,
vol. 4. IEEE, 2002, pp. 276–280.

12

[31] S. R. Bulò, A. Lourenço, A. Fred, and M. Pelillo, “Pairwise probabilistic clustering using evidence accumulation,” in Joint IAPR International Workshops
on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). Springer, 2010, pp. 395–404.
[32] A. Lourenço, S. R. Bulò, N. Rebagliati, A. L. Fred, M. A. Figueiredo, and M. Pelillo, “Probabilistic evidence accumulation for clustering ensembles.”
in ICPRAM, 2013, pp. 58–67.
[33] ——, “Probabilistic consensus clustering using evidence accumulation,” Machine Learning, vol. 98, no. 1-2, pp. 331–357, 2015.
[34] A. Ng, Y. Weiss, and M. Jordan, “On spectral clustering: Analysis and an algorithm,” in Proc. Neural Information Processing Systems, 2001.
[35] R.
Vershynin,
A
Course
in
High
Dimensional
Probability,
2016.
[Online].
Available:
www-personal.umich.edu/~romanv/teaching/2015-16/626/HDP-book.pdf
[36] D. Zhang and L. Balzano, “Global convergence of a grassmannian gradient descent algorithm for subspace estimation,” in Proceedings of the 19th
International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, A. Gretton and C. C. Robert, Eds.,
vol. 51. Cadiz, Spain: PMLR, 09–11 May 2016, pp. 1460–1468. [Online]. Available: http://proceedings.mlr.press/v51/zhang16b.html
[37] D. Arthur and S. Vassilvitskii, “k-means++: The advantages of careful seeding,” in Proceedings of the eighteenth annual ACM-SIAM symposium on
Discrete algorithms. Society for Industrial and Applied Mathematics, 2007, pp. 1027–1035.
[38] P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in Proceedings of the forty-fifth annual ACM
symposium on Theory of computing. ACM, 2013, pp. 665–674.
[39] C. Tomasi and T. Kanade, “Shape and motion from image streams under orthography,” Int’l J. Computer Vision, vol. 9, no. 2, pp. 137–154, 1992.
[40] R. Heckel, E. Agustsson, and H. Bolcskei, “Neighborhood selection for thresholding-based subspace clustering,” in Acoustics, Speech and Signal
Processing (ICASSP), 2014 IEEE International Conference on. IEEE, 2014, pp. 6761–6765.
[41] C.
T.
Group.
ETH
Zurich
Department
of
Information
Technology
and
Electrical
Engineering.
[Online].
Available:
http://www.nari.ee.ethz.ch/commth/research/
[42] K. Lee, J. Ho, and D. Kriegman, “Acquiring linear subspaces for face recognition under variable lighting,” IEEE Trans. Pattern Anal. Mach. Intelligence,
vol. 27, no. 5, pp. 684–698, 2005.
[43] S. A. Nene, S. K. Nayar, and H. Murase, “Columbia object image library (COIL-20),” Columbia University, Tech. Rep., 1996.
[44] ——, “Columbia object image library (COIL-100),” Columbia University, Tech. Rep., 1996.
[45] D. Cai, X. He, J. Han, and T. S. Huang, “Graph regularized non-negative matrix factorization for data representation,” IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 33, no. 8, pp. 1548–1560, 2011.
[46] J. Bruna and S. Mallat, “Invariant scattering convolution networks,” IEEE transactions on pattern analysis and machine intelligence, vol. 35, no. 8, pp.
1872–1886, 2013.

