基于TL1范数约束的子空间聚类方法

李海洋; 王恒远

doi:10.11999/JEIT170193

基于TL1范数约束的子空间聚类方法

doi: 10.11999/JEIT170193

李海洋¹,
王恒远¹

基金项目:

国家自然科学基金(11271297)，陕西省自然科学基金(2015JM1020)

计量
- 文章访问数: 1190
- HTML全文浏览量: 133
- PDF下载量: 279
- 被引次数: 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范数应用于子空间聚类的研究中，提出基于TL1范数约束的子空间聚类优化模型。尽管该优化模型是非凸的，在无噪音的情形下，证明了它的最优解为具有块对角结构的系数矩阵，这对随后进行的谱聚类提供了理论保证；在有噪声的情形下，它的约束条件等价于以干净数据为字典的优化模型，因而求解出的系数矩阵提高了聚类的精确度。进一步，利用增广拉格朗日-交替方向乘子方法给出该优化模型的求解方法。实验结果表明，基于TL1范数的子空间聚类方法不仅增强了系数矩阵的稀疏性，而且在聚类精确度，对噪音的鲁棒性方面要优于低秩子空间聚类方法和稀疏子空间聚类方法。
- TL1范数 /
- 子空间聚类方法 /
- 稀疏 /
- 低秩 /
- 谱聚类
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]. 电子与信息学报, 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.

施引文献

资源附件(0)

访问统计