THE 1-LAPLACIAN CHEEGER CUT: THEORY AND ALGORITHMS

被引：19

作者：

Chang, K. C. ^{[1
]}

Shao, Sihong

Zhang, Dong

机构：

[1] Peking Univ, LMAM, Beijing 100871, Peoples R China

来源：

JOURNAL OF COMPUTATIONAL MATHEMATICS | 2015年 / 33卷 / 05期

基金：

中国国家自然科学基金;

关键词：

Spectral graph theory; Spectral clustering; 1-Laplace operator; Graph Laplacian; Eigenvalue problems; Cheeger constant; Graph cut; Optimization; Convergence;

D O I：

10.4208/jcm.1506-m2014-0164

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend (CD) framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power (IP) method and the steepest descent (SD) method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.

引用

页码：443 / 467

页数：25

共 20 条

[1]

[Anonymous], 2013, Advances in Neural Information Processing Systems

[2]

[Anonymous], 1970, Problems in Analysis

[3]

[Anonymous], 2011, Advances in Neural Information Processing Systems

[4]

[Anonymous], 2010, Adv. Neural Inf. Process.

[5] Distributed optimization and statistical learning via the alternating direction method of multipliers [J].

Boyd S. ;

Parikh N. ;

Chu E. ;

Peleato B. ;

Eckstein J. .

Foundations and Trends in Machine Learning, 2010, 3 (01) :1-122

[6]

Bresson X, 2012, ADV NEURAL INFORM PR, V25, P1385

[7]

Buhler T., 2009, P 26 ANN INT C MACH, P81, DOI DOI 10.1145/1553374.1553385

[8]

BUHLER T., 2013, P 30 INT C MACH LEAR, P624

[9] A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging [J].

Chambolle, Antonin ;

Pock, Thomas .

JOURNAL OF MATHEMATICAL IMAGING AND VISION, 2011, 40 (01) :120-145

[10]

Chang K.C., 1985, CRITICAL POINT THEOR

← 1 2 →