TY - JOUR
T1 - Subspace Learning by ℓ0 -Induced Sparsity
AU - Yang, Yingzhen
AU - Feng, Jiashi
AU - Jojic, Nebojsa
AU - Yang, Jianchao
AU - Huang, Thomas S.
N1 - Funding Information:
This material is based upon work supported by the findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The work of Yingzhen Yang was supported in part by an IBM gift grant to Beckman Institute, UIUC. The work of Jiashi Feng was partially supported by National University of Singapore startup Grant R-263-000-C08-133 and Ministry of Education of Singapore AcRF Tier One Grant R-263-000-C21-112.
Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - 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 Intell 35(11):2765–2781, 2013) with the sparsity induced by the ℓ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 ℓ0-induced sparse subspace clustering (ℓ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 ℓ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 ℓ0 sparse representation problem of ℓ0-SSC. A novel approximate algorithm named Approximate ℓ0-SSC (Aℓ0-SSC) is developed which employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of ℓ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 Aℓ0-SSC compared to other competing clustering methods. Furthermore, we extend ℓ0-SSC to semi-supervised learning by performing label propagation on the sparse similarity matrix learnt by Aℓ0-SSC and demonstrate the effectiveness of the resultant semi-supervised learning method termed ℓ0-sparse subspace label propagation (ℓ0-SSLP).
AB - 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 Intell 35(11):2765–2781, 2013) with the sparsity induced by the ℓ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 ℓ0-induced sparse subspace clustering (ℓ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 ℓ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 ℓ0 sparse representation problem of ℓ0-SSC. A novel approximate algorithm named Approximate ℓ0-SSC (Aℓ0-SSC) is developed which employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of ℓ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 Aℓ0-SSC compared to other competing clustering methods. Furthermore, we extend ℓ0-SSC to semi-supervised learning by performing label propagation on the sparse similarity matrix learnt by Aℓ0-SSC and demonstrate the effectiveness of the resultant semi-supervised learning method termed ℓ0-sparse subspace label propagation (ℓ0-SSLP).
KW - Proximal gradient descent
KW - Sparse similarity matrix
KW - Subspace-sparse representation
KW - ℓ-Induced sparse subspace clustering
UR - http://www.scopus.com/inward/record.url?scp=85049941293&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049941293&partnerID=8YFLogxK
U2 - 10.1007/s11263-018-1092-4
DO - 10.1007/s11263-018-1092-4
M3 - Article
AN - SCOPUS:85049941293
SN - 0920-5691
VL - 126
SP - 1138
EP - 1156
JO - International Journal of Computer Vision
JF - International Journal of Computer Vision
IS - 10
ER -