Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method | Science China Information Sciences Skip to main content
Springer Nature Link
Log in

Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method

多路归一化割谱聚类方法中规范Laplace矩阵的扰动分析

  • Research Paper
  • Published:
Science China Information Sciences Aims and scope Submit manuscript

Abstract

In this paper, we present a perturbation analysis for the matrices in the multiway normalized cut spectral clustering method based on the matrix perturbation theory. The analytical results show that the eigenvalues and the eigenspaces of the normalized Laplacian matrices are continuous. Therefore, clustering algorithms can be designed according to the special properties of the normalized Laplacian matrices in the ideal case and the method can be extended to the general case based on the continuity of the eigenvalues and the eigenspaces of the normalized Laplacian matrices. The numerical results are consistent with the theoretical results.

摘要

创新点: 本文利用矩阵扰动理论对多路归一化割谱聚类方法用到的矩阵进行了扰动分析. 分析结果表明多路归一化割谱聚类方法用到的矩阵的特征值和特征子空间具有连续性. 因此, 在理想情形下根据多路归一化割谱聚类方法用到的矩阵的特殊性质划分数据, 再将结果推广到一般情形是合理的. 值得一提的是, 本文对非对称规范Laplace矩阵进行了扰动分析. 另外, 本文给出了谱聚类的划分结果保持不变的扰动上限.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Meilă M, Shi J B. Learning segmentation by random walks. In: Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2001. 873–879

    Google Scholar 

  2. Shi J B, Malik J. Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell, 2000, 22: 888–905

    Article  Google Scholar 

  3. Wu Z Y, Leahy R. A optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Trans Pattern Anal Mach Intell, 1993, 15: 1101–1113

    Article  Google Scholar 

  4. Hagen L, Kahng A. New spectral methods for ratio cut partitioning and clustering. IEEE Trans Comput Aided Des, 1992, 11: 1074–1085

    Article  Google Scholar 

  5. Sarkar S, Soundararajan P. Supervised learning of large perceptual organization: graph spectral partitioning and learning automata. IEEE Trans Pattern Anal Mach Intell, 2000, 22: 504–525

    Article  Google Scholar 

  6. Gu M, Zha H Y, Ding C, et al. Spectral Relaxation Models and Structure Analysis for K-way Graph Clustering and Bi-clustering. Pennsylvania State University Technical Report. 2001

    Google Scholar 

  7. Meilă M, Xu L. Multiway Cuts and Spectral Clustering. University of Washington Technical Report. 2003

    Google Scholar 

  8. Ng A, Jordan M, Weiss Y. On spectral clustering: analysis and an Algorithm. In: Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2002. 849–856

    Google Scholar 

  9. Verma D, Meilă M. A Comparison of Spectral Clustering Algorithms. University of Washington Technical Report. 2003

    Google Scholar 

  10. Luxburg U. A tutorial on spectral clustering. Stat Comput, 2007, 17: 395–416

    Article  MathSciNet  Google Scholar 

  11. Tian Z, Li X, Ju Y. Spectral clustering based on matrix perturbation theory. Sci China Ser-F: Inf Sci, 2007, 50: 63–81

    Article  MathSciNet  MATH  Google Scholar 

  12. Huang L, Yan D H, Jordan M, et al. Spectral clustering with perturbed data. In: Advances in Neural Information Processing Systems. New York: Curran Associates, 2009. 705–712

    Google Scholar 

  13. Rohe K, Chatterjee S, Yu B. Spectral clustering and the high-dimensional stochastic block model. Ann Stat, 2011, 39: 1878–1915

    Article  MathSciNet  MATH  Google Scholar 

  14. Balakrishnan S, Xu M, Krishnamurthy A, et al. Noise thresholds for spectral clustering. In: Advances in Neural Information Processing Systems. New York: Curran Associates, 2011. 954–962

    Google Scholar 

  15. Stewart W, Sun J G. Matrix Perturbation Theory. Boston: Academic Press, 1990. 189–283

    MATH  Google Scholar 

  16. Bhatia B. Matrix Analysis. New York: Springer, 1997. 212–214

    Book  Google Scholar 

  17. Golub G, Loan C. Matrix Computations. 3rd ed. Baltimore and London: Johns Hopkins University Press, 1996. 250–253

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Economics and Management, Inner Mongolia University, Hohhot, 010021, China

    SuMuYa Borjigin

  2. Institute of Systems Engineering, Dalian University of Technology, Dalian, 116024, China

    SuMuYa Borjigin & ChongHui Guo

Authors
  1. SuMuYa Borjigin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. ChongHui Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to SuMuYa Borjigin or ChongHui Guo.

Electronic supplementary material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Borjigin, S., Guo, C. Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method. Sci. China Inf. Sci. 57, 1–17 (2014). https://doi.org/10.1007/s11432-014-5156-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11432-014-5156-y

Keywords

关键词

Search

Navigation