nips nips2012 nips2012-85 nips2012-85-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xavier Bresson, Thomas Laurent, David Uminsky, James V. Brecht
Abstract: This paper provides both theoretical and algorithmic results for the 1 -relaxation of the Cheeger cut problem. The 2 -relaxation, known as spectral clustering, only loosely relates to the Cheeger cut; however, it is convex and leads to a simple optimization problem. The 1 -relaxation, in contrast, is non-convex but is provably equivalent to the original problem. The 1 -relaxation therefore trades convexity for exactness, yielding improved clustering results at the cost of a more challenging optimization. The first challenge is understanding convergence of algorithms. This paper provides the first complete proof of convergence for algorithms that minimize the 1 -relaxation. The second challenge entails comprehending the 1 energy landscape, i.e. the set of possible points to which an algorithm might converge. We show that 1 -algorithms can get trapped in local minima that are not globally optimal and we provide a classification theorem to interpret these local minima. This classification gives meaning to these suboptimal solutions and helps to explain, in terms of graph structure, when the 1 -relaxation provides the solution of the original Cheeger cut problem. 1
[1] X. Bresson, X.-C. Tai, T.F. Chan, and A. Szlam. Multi-Class Transductive Learning based on 1 Relaxations of Cheeger Cut and Mumford-Shah-Potts Model. UCLA CAM Report, 2012.
[2] T. B¨ hler and M. Hein. Spectral Clustering Based on the Graph p-Laplacian. In International u Conference on Machine Learning, pages 81–88, 2009.
[3] A. Chambolle and T. Pock. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011.
[4] J. Cheeger. A Lower Bound for the Smallest Eigenvalue of the Laplacian. Problems in Analysis, pages 195–199, 1970.
[5] F. R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.
[6] M. Hein and T. B¨ hler. An Inverse Power Method for Nonlinear Eigenproblems with Apu plications in 1-Spectral Clustering and Sparse PCA. In In Advances in Neural Information Processing Systems (NIPS), pages 847–855, 2010.
[7] M. Hein and S. Setzer. Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts. In In Advances in Neural Information Processing Systems (NIPS), 2011.
[8] R.R. Meyer. Sufficient conditions for the convergence of monotonic mathematical programming algorithms. Journal of Computer and System Sciences, 12(1):108 – 121, 1976.
[9] S. Rangapuram and M. Hein. Constrained 1-Spectral Clustering. In International conference on Artificial Intelligence and Statistics (AISTATS), pages 1143–1151, 2012.
[10] J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22(8):888–905, 2000.
[11] G. Strang. Maximal Flow Through A Domain. Mathematical Programming, 26:123–143, 1983.
[12] A. Szlam and X. Bresson. Total variation and cheeger cuts. In Proceedings of the 27th International Conference on Machine Learning, pages 1039–1046, 2010.
[13] L. Zelnik-Manor and P. Perona. Self-tuning Spectral Clustering. In In Advances in Neural Information Processing Systems (NIPS), 2004. 9