Selective Sampling-based Scalable Sparse Subspace Clustering
Selective Sampling-based Scalable Sparse Subspace Clustering
复制标题
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shin Matsushima;Maria Brbic
中科院分区：
文献类型：
--
作者：
Shin Matsushima;Maria Brbic
稀疏子空间聚类(SSC)将每个数据点表示为数据集中其他数据点的稀疏线性组合。在表示学习步骤中，SSC找到数据点的低维表示，而在谱聚类步骤中，数据点根据底层子空间被聚类。然而，这两个步骤都存在计算和存储复杂性高的问题，这阻碍了SSC在大规模数据集上的应用。为了克服这一局限性，我们引入了基于选择性采样的可伸缩稀疏子空间聚类(S5C)算法，该算法根据近似的子梯度选择子样本，并根据时间和内存需求与数据点的数量线性缩放。除了计算上的优势，我们还从理论上保证了S5C算法的正确性。我们的理论结果在子样本数量有限的情况下为SSC提供了新的贡献。大量的实验结果证明了该方法的有效性。
Sparse subspace clustering (SSC) represents each data point as a sparse linear combination of other data points in the dataset. In the representation learning step SSC finds a lower dimensional representation of data points, while in the spectral clustering step data points are clustered according to the underlying subspaces. However, both steps suffer from high computational and memory complexity, preventing the application of SSC to large-scale datasets. To overcome this limitation, we introduce Selective Sampling-based Scalable Sparse Subspace Clustering (S5C) algorithm which selects subsamples based on the approximated subgradients and linearly scales with the number of data points in terms of time and memory requirements. Along with the computational advantages, we derive theoretical guarantees for the correctness of S5C. Our theoretical result presents novel contribution for SSC in the case of limited number of subsamples. Extensive experimental results demonstrate effectiveness of our approach.