基于TL1范數(shù)約束的子空間聚類方法

李海洋; 王恒遠

doi:10.11999/JEIT170193

基于TL1范數(shù)約束的子空間聚類方法

doi: 10.11999/JEIT170193

李海洋¹,
王恒遠¹

基金項目:

國家自然科學(xué)基金(11271297)，陜西省自然科學(xué)基金(2015JM1020)

計量
- 文章訪問數(shù): 1212
- HTML全文瀏覽量: 136
- PDF下載量: 279
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2017-03-03
- 修回日期: 2017-06-27
- 刊出日期: 2017-10-19

Subspace Clustering Method Based on TL1 Norm Constraints

LI Haiyang¹,
WANG Hengyuan¹

Funds:

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

摘要

摘要: 該文將TL1范數(shù)應(yīng)用于子空間聚類的研究中，提出基于TL1范數(shù)約束的子空間聚類優(yōu)化模型。盡管該優(yōu)化模型是非凸的，在無噪音的情形下，證明了它的最優(yōu)解為具有塊對角結(jié)構(gòu)的系數(shù)矩陣，這對隨后進行的譜聚類提供了理論保證；在有噪聲的情形下，它的約束條件等價于以干凈數(shù)據(jù)為字典的優(yōu)化模型，因而求解出的系數(shù)矩陣提高了聚類的精確度。進一步，利用增廣拉格朗日-交替方向乘子方法給出該優(yōu)化模型的求解方法。實驗結(jié)果表明，基于TL1范數(shù)的子空間聚類方法不僅增強了系數(shù)矩陣的稀疏性，而且在聚類精確度，對噪音的魯棒性方面要優(yōu)于低秩子空間聚類方法和稀疏子空間聚類方法。
- TL1范數(shù) /
- 子空間聚類方法 /
- 稀疏 /
- 低秩 /
- 譜聚類
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

HTML全文

參考文獻(33)

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]. 電子與信息學(xué)報, 2016, 38(11): 2811-2818. doi: 10.11999/JEIT160009.

王衛(wèi)衛(wèi), 李小平, 馮象初, 等. 稀疏子空間聚類綜述[J]. 自動化學(xué)報, 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]. 自動化學(xué)報, 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]. 計算機應(yīng)用, 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.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計