ℓ⁰-sparse subspace clustering

Subspace clustering methods with sparsity prior, such as Sparse Subspace Clustering (SSC) [1], are effective in partitioning the data that lie in a union of subspaces. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. These assumptions are not guaranteed to hold in practice and they limit the application of existing sparse subspace clustering methods. In this paper, we propose ℓ⁰-induced sparse subspace clustering (ℓ⁰-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that subspace-sparse representation, a key element in subspace clustering, can be obtained by ℓ⁰-SSC for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We also present the "no free lunch" theorem that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding ℓ⁰ problem of ℓ⁰-SSC. We develop a novel approximate algorithm named Approximate ℓ⁰-SSC (Aℓ⁰-SSC) that employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of ℓ⁰-SSC with theoretical guarantee, and the sub-optimal solution is used to build a sparse similarity matrix for clustering. Extensive experimental results on various data sets demonstrate the superiority of Aℓ⁰-SSC compared to other competing clustering methods.