Subspace Clustering Method Based on TL1 Norm Constraints

LI Haiyang; WANG Hengyuan

doi:10.11999/JEIT170193

Volume 39 Issue 10

Oct. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(10): 2428-2436

LI Haiyang, WANG Hengyuan. Subspace Clustering Method Based on TL1 Norm Constraints[J]. Journal of Electronics & Information Technology, 2017, 39(10): 2428-2436. doi: 10.11999/JEIT170193

Citation:

LI Haiyang, WANG Hengyuan. Subspace Clustering Method Based on TL1 Norm Constraints[J]. Journal of Electronics & Information Technology, 2017, 39(10): 2428-2436. doi: 10.11999/JEIT170193

LI Haiyang, WANG Hengyuan. Subspace Clustering Method Based on TL1 Norm Constraints[J]. Journal of Electronics & Information Technology, 2017, 39(10): 2428-2436. doi: 10.11999/JEIT170193

Citation:

LI Haiyang, WANG Hengyuan. Subspace Clustering Method Based on TL1 Norm Constraints[J]. Journal of Electronics & Information Technology, 2017, 39(10): 2428-2436. doi: 10.11999/JEIT170193

PDF( 2008 KB)

Subspace Clustering Method Based on TL1 Norm Constraints

doi: 10.11999/JEIT170193 cstr: 32379.14.JEIT170193

LI Haiyang¹,
WANG Hengyuan¹

Funds:

The National Natural Science Foundation of China (11271297), The Natural Science Foundation of Shaanxi Province (2015JM1020)

Received Date: 2017-03-03
Rev Recd Date: 2017-06-27
Publish Date: 2017-10-19

Abstract

Abstract

The TL1 norm is applied to propose a new optimization model for the study of subspace clustering. Although the optimization is nonconvex, in the case of non-noise, it proves that the optimal solution of the proposed model is the coefficient matrix with block-diagonal structure, which provides the theoretical guarantee for the latter spectral clustering. In the case of dealing with noise, the constraint condition of this model is presented to be equivalent with the optimal model using the corrected data as the dictionary, which contributes to improving the clustering accuracy. Then, the alternating direction method of Lagrangian multipliers is applied to solving the unknown matrices. Experimental results show that subspace clustering method based on TL1 norm not only enhances the sparsity of coefficient matrix, but also is superior to low-rank subspace clustering and sparse subspace clustering method in terms of clustering accuracy and robustness to noise.
- TL1 norm,
- Subspace clustering method,
- Sparse,
- Low-rank,
- Spectral clustering

FullText(HTML)

References(33)

References

ZHANG Tao, TANG Zhenmin, and L Jianyong. Improved algorithm based on low rank representation for subspace clustering[J]. Journal of Electronics Information Technology, 2016, 38(11): 2811-2818. doi: 10.11999/JEIT 160009.

张涛, 唐振民, 吕建勇. 一种基于低秩表示的子空间聚类改进算法[J]. 电子与信息学报, 2016, 38(11): 2811-2818. doi: 10.11999/JEIT160009.

王卫卫, 李小平, 冯象初, 等. 稀疏子空间聚类综述[J]. 自动化学报, 2015, 41(8): 1373-1384. doi: 10.16383/j.aas.2015. c140891.

WANG Weiwei, LI Xiaoping, FENG Xiangchu, et al. A survey on sparse subspace clustering[J]. Acta Automatica Sinica, 2015, 41(8): 1373-1384. doi: 10.16383/j.aas.2015. c140891.

YANG A, WRIGHT J, MA Y, et al. Unsupervised segmentation of natural images via lossy data compression[J]. Computer Vision and Image Understanding, 2008, 110(2): 212-225. doi: 10.1016/j.cviu.2007.07.005.

WRIGHT J, MAIRAL J, MA Y, et al. Sparse representation for computer vision and pattern recognition[J]. Proceedings of the IEEE, 2010, 98(6): 1031-1044. doi: 10.1109/JPROC. 2010.2044470.

LI C G, YOU C, and VIDAL R. Structured sparse subspace clustering: A joint affinity learning and subspace clustering framework[J]. IEEE Transactions on Image Processing, 2017, 26(6): 2988-3001. doi: 10.1109/TIP.2017.2691557.

VIDAL R. Subspace clustering[J]. IEEE Signal Processing Magazine, 2011, 28(2): 52-68. doi: 10.1109/MSP.2010. 939739.

ELHAMIFAR E and VIDAL R. Sparse subspace clustering [C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, 2009: 2790-2797. doi: 10.1109/CVPR.2009.5206547.

ELHAMIFAR E and VIDAL R. Sparse subspace clustering: Algorithm, theory, and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2765-2781. doi: 10.1109/TPAMI.2013.57.

LIU G C, LIN Z C, YAN S C, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 171-184. doi: 10.1109/TPAMI.2012.88.

LIU G C, LIN Z C, and YU Y. Robust subspace segmentation by low-rank representation[C]. Proceedings of the International Conference on Machine Learning, Haifa, Israel, 2010: 663-670.

NG A Y, JORDAN M, and WEISS Y. On spectral clustering: Analysis and an algorithm[C]. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, Canada, 2001: 849-856.

PAN J, MATHIEU S, and HONG L. Efficient dense subspace clustering[C]. IEEE Winter Conference on Applications of Computer Vision, USA, 2014: 461-468. doi: 10.1109/WACV.2014.6836065.

ZHUANG L S, MA Y, LIN Z C, et al. Non-negative low-rank and sparse graph for semi-supervised learning[C]. IEEE Conference on Computer Vision and Pattern Recognition, Rhode Island, 2012: 2328-2335. doi: 10.1109/CVPR.2012. 6247944.

PATEL V M, NGUYEN H V, and VIDAL R. Latent space sparse and low-rank subspace clustering[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(4): 691-701. doi: 10.1109/JSTSP.2015.2402643.

李波, 卢春园, 冷成财, 等. 基于局部图拉普拉斯约束的鲁棒低秩表示聚类方法[J]. 自动化学报, 2015, 41(11): 1971-1980. doi: 10.16383/j.aas.2015.c150031.

LI Bo, LU Chunyuan, LENG Chengcai, et al. Robust low rank subspace clustering based on local graph laplace constraint[J]. Acta Automatica Sinica, 2015, 41(11): 1971-1980. doi: 10.16383/j.aas.2015.c150031.

NIKOLOVA M. Local strong homogeneity of a regularized estimator[J]. SIAM Journal on Applied Mathematics, 2000, 61(2): 633-658. doi: 10.1137/S0036139997327794.

L J, and FAN Y. A unified approach to model selection and sparse recovery using regularized least squares[J]. The Annals of Statistics, 2009, 37(6A): 3498-3528. doi: 10.1214/ 09-AOS683.

ZHANG S, YIN P H, and JACK X. Transformed schatten iterative thresholding algorithms for matrix rank minimization and applications[J]. Arxiv Preprint, 2015, 1506. 04444. https://www.researchgate.net/publication/2784138 40.

ZHANG S and JACK X. Minimization of transformed L1 penalty: Theory, difference of convex function algorithm, and robust application in compressed sensing[J]. Arxiv Preprint, 2016, 1411.5735v3. https://arxiv.org/abs/1411.5735.

HORN R and JOHNSON C. Topics in Matrix Analysis[M]. Cambridge University Press, 1991: 144-163.

LIN Z C, CHEN M, and MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[R]. UIUC Technical Report UILU-ENG-09-2215, 2009.

吴杰祺, 李晓宇, 袁晓彤, 等. 利用坐标下降实行并行稀疏子空间聚类[J]. 计算机应用, 2016, 36(2): 372-376. doi: 10.11772/j.issn.1001-9081.2016.02.0372.

WU Jieqi, LI Xiaoyu, YUAN Xiaotong, et al. Parallel sparse subspace clustering via coordinate descent minimization[J]. Journal of Computer Applications, 2016, 36(2): 372-376. doi: 10.11772/j.issn.1001-9081.2016.02.0372.

VIDAL R and FAVARO P, A closed form solution to robust subspace estimation and clustering[C]. IEEE Conference on Computer Vision and Pattern Recognition, USA, 2011, 1801-1807. doi: 10.11091/CVPR.2011.5995365.

BERTSEKAS D. Constrained Optimization and Lagrange Multiplier Methods[M]. Belmont, MA, USA: Athena Scientific, 1996: 326-340.

CANDES E J, LI X D, MA Y, et al. Robust principal component analysis[J]. Journal of the ACM, 2010, 58(3): 11. doi: 10.1145/1970392.1970395.

GEORGHIADES A, BELHUMEUR P, and KRIEGMAN D. From few to many: Illumination cone models for face recognition under variable lighting and pose[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 23(6): 643-660. doi: 10.1109/34.927464.

YAN J Y and POLLEYFEYS M. A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate[C]. Proceedings of the European Conference on Computer Vision, Graz, Austria, 2006: 94-106. doi: 10.1007/11744085_8.

FENG J S, LIN Z C, XU H, et al. Robust subspace segmentation with block-diagonal prior[C]. Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, Columbus, USA, 2014: 3818-3825. doi: 10.1109/CVPR.2014.482.

VIDAL R and FAVARO P. Low-rank subspace clustering (LRSC)[J]. Pattern Recognition Letters, 2014, 43: 47-61. doi: 10.1016/j.patrec.2013.08.006.

Relative Articles

Supplements(0)

Cited By

Proportional views