Subspace Learning by l0-Induced Sparsity

doi:10.1007/s11263-018-1092-4

Subspace Learning by l0-Induced Sparsity

2018-07-17

11

PRE

AI

DOI：10.1007/s11263-018-1092-4

原文链接

原文求助

摘要

En 中文

Subspace clustering methods partition the data that lie in or close to a union of subspaces in accordance with the subspace structure. Such methods with sparsity prior, such as sparse subspace clustering (SSC) (Elhamifar and Vidal in IEEE Trans Pattern Anal Mach Intel) 35(11):2765-2781, 2013) with the sparsity induced by the a l(1)-norm, are demonstrated to be effective in subspace clustering. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. However, 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 l(0)-induced sparse subspace clustering (l(0)-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that l(0)-SSC guarantees the subspace-sparse representation, a key element in subspace clustering, 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 which shows that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding l(0) sparse representation problem of l(0)-SSC. A novel approximate algorithm named Approximate l(0)-SSC (Al-0-SSC) is developed which employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of l(0)-SSC with theoretical guarantee. The sub-optimal solution is used to build a sparse similarity matrix upon which spectral clustering is performed for the final clustering results. Extensive experimental results on various data sets demonstrate the superiority of Al-0-SSC compared to other competing clustering methods. Furthermore, we extend l(0)-SSC to semi-supervised learning by performing label propagation on the sparse similarity matrix learnt by Al-0-SSC and demonstrate the effectiveness of the resultant semi-supervised learning method termed l(0)-sparse subspace label propagation (l(0)-SSLP).

Keyword:

l(0)-Induced sparse subspace clustering (l(0)-SSC)

Subspace-sparse representation

Proximal gradient descent

Sparse similarity matrix

Subspace Learning by l0-Induced Sparsity

摘要

AI总结

期刊

机构