Subspace clustering is the unsupervised grouping of points lying near a union
of low-dimensional linear subspaces. Algorithms based directly on geometric
properties of such data tend to either provide poor empirical performance, lack
theoretical guarantees, or depend heavily on their initialization. We present a
novel geometric approach to the subspace clustering problem that leverages
ensembles of the K-subspaces (KSS) algorithm via the evidence accumulation
clustering framework. Our algorithm, referred to as ensemble K-subspaces
(EKSS), 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 prove general recovery guarantees for any algorithm that
forms an affinity matrix with entries close to a monotonic transformation of
pairwise absolute inner products. We then show that a specific instance of EKSS
results in an affinity matrix with entries of this form, and hence our proposed
algorithm can provably recover subspaces under similar conditions to
state-of-the-art algorithms. The finding is, to the best of our knowledge, the
first recovery guarantee for evidence accumulation clustering and for KSS
variants. We show on synthetic data that our method performs well in the
traditionally challenging settings of subspaces with large intersection,
subspaces with small principal angles, and noisy data. Finally, we evaluate our
algorithm on six common benchmark datasets and show that unlike existing
methods, EKSS achieves excellent empirical performance when there are both a
small and large number of points per subspace.

我们提出了一种基于集合 K 子空间 (EKSS) 的几何方法，该算法通过证据积累聚类框架，形成一个共同关联矩阵，该矩阵的 (i，j) th 项是由多次运行具有随机初始化的 KSS 聚类算法将点 i 和 j 配对在一起的次数。我们表明，当一个算法形成的亲和力矩阵的具有和绝对内积的单调变换接近的条目时，该算法可以提供恢复保证。

利用 $K$ 子空间集成的子空间聚类

Subspace Clustering using Ensembles of $K$-Subspaces

Many applications require recovering a ground truth low-rank matrix from
noisy observations of the entries, which in practice is typically formulated as
a weighted low-rank approximation problem and solved by non-convex optimization
heuristics such as alternating minimization. In this paper, we provide provable
recovery guarantee of weighted low-rank via a simple alternating minimization
algorithm. In particular, for a natural class of matrices and weights and
without any assumption on the noise, we bound the spectral norm of the
difference between the recovered matrix and the ground truth, by the spectral
norm of the weighted noise plus an additive error that decreases exponentially
with the number of rounds of alternating minimization, from either
initialization by SVD or, more importantly, random initialization. These
provide the first theoretical results for weighted low-rank via alternating
minimization with non-binary deterministic weights, significantly generalizing
those for matrix completion, the special case with binary weights, since our
assumptions are similar or weaker than those made in existing works.
Furthermore, this is achieved by a very simple algorithm that improves the
vanilla alternating minimization with a simple clipping step.
The key technical challenge is that under non-binary deterministic weights,
na\"ive alternating steps will destroy the incoherence and spectral properties
of the intermediate solutions, which are needed for making progress towards the
ground truth. We show that the properties only need to hold in an average sense
and can be achieved by the clipping step.
We further provide an alternating algorithm that uses a whitening step that
keeps the properties via SDP and Rademacher rounding and thus requires weaker
assumptions. This technique can potentially be applied in some other
applications and is of independent interest.

本文提出一种简单的交替最小化算法，提供了带权重低秩矩阵恢复的可证明的等保障，并不需要关于噪声的假设，其误差随交替次数按指数级递减，初始矩阵可以由 SVD 或随机初始化得到，这是一种非常简单的算法，可以显着扩展矩阵补全的结果，特别是那些存在于现有研究工作中的二进制权重问题。