Selective Sampling-based Scalable Sparse Subspace Clustering

2019-12-01 · NeurIPS 2019 12 · Shin Matsushima, Maria Brbic

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.

📄 PDF Abstract BibTeX

Code (1)

smatsus/S5C 공식 구현

Tasks

ClusteringRepresentation Learning

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Scalable Sparse Subspace Clustering

2013-06-01 · CVPR 2013 6 · Xi Peng, Lei Zhang, Zhang Yi

In this paper, we address two problems in Sparse Subspace Clustering algorithm (SSC), i.e., scalability issue and out-of-sample problem. SSC constructs a sparse similarity graph for spectral clustering by using sp-minimi…

Clustering Image Clustering Motion Segmentation Online Clustering

Scalable Sparse Subspace Clustering via Ordered Weighted $\ell_1$ Regression

2018-07-10 · Urvashi Oswal, Robert Nowak

The main contribution of the paper is a new approach to subspace clustering that is significantly more computationally efficient and scalable than existing state-of-the-art methods. The central idea is to modify the regr…

Clustering regression

Stochastic Sparse Subspace Clustering

2020-05-04 · CVPR 2020 6 · Ying Chen, Chun-Guang Li, Chong You

State-of-the-art subspace clustering methods are based on self-expressive model, which represents each data point as a linear combination of other data points. By enforcing such representation to be sparse, sparse subspa…

Clustering

Unbiased Sparse Subspace Clustering By Selective Pursuit

2016-09-16 · Hanno Ackermann, Michael Ying Yang, Bodo Rosenhahn

Sparse subspace clustering (SSC) is an elegant approach for unsupervised segmentation if the data points of each cluster are located in linear subspaces. This model applies, for instance, in motion segmentation if some r…

Clustering Motion Segmentation Segmentation

Sparse-Dense Subspace Clustering

2019-10-20 · Shuai Yang, Wenqi Zhu, Yuesheng Zhu

Subspace clustering refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Current subspace clustering approaches are usually based on a two-stage framework. In the first sta…