nips nips2013 nips2013-202 nips2013-202-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xavier Bresson, Thomas Laurent, David Uminsky, James von Brecht
Abstract: Ideas from the image processing literature have recently motivated a new set of clustering algorithms that rely on the concept of total variation. While these algorithms perform well for bi-partitioning tasks, their recursive extensions yield unimpressive results for multiclass clustering tasks. This paper presents a general framework for multiclass total variation clustering that does not rely on recursion. The results greatly outperform previous total variation algorithms and compare well with state-of-the-art NMF approaches. 1
[1] Raman Arora, M Gupta, Amol Kapila, and Maryam Fazel. Clustering by left-stochastic matrix factorization. In International Conference on Machine Learning (ICML), pages 761–768, 2011.
[2] A. Bertozzi and A. Flenner. Diffuse Interface Models on Graphs for Classification of High Dimensional Data. Multiscale Modeling and Simulation, 10(3):1090–1118, 2012.
[3] X. Bresson, T. Laurent, D. Uminsky, and J. von Brecht. Convergence and energy landscape for cheeger cut clustering. In Advances in Neural Information Processing Systems (NIPS), pages 1394–1402, 2012.
[4] 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.
[5] T. B¨ hler and M. Hein. Spectral Clustering Based on the Graph p-Laplacian. In International u Conference on Machine Learning (ICML), pages 81–88, 2009.
[6] 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.
[7] J. Cheeger. A Lower Bound for the Smallest Eigenvalue of the Laplacian. Problems in Analysis, pages 195–199, 1970.
[8] 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.
[9] Chris Ding, Xiaofeng He, and Horst D Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proc. SIAM Data Mining Conf, number 4, pages 606– 610, 2005.
[10] C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner, and A. G. Percus. Fast multiclass segmentation using diffuse interface methods on graphs. Submitted, 2013.
[11] M. Hein and T. B¨ hler. An Inverse Power Method for Nonlinear Eigenproblems with Applicau tions in 1-Spectral Clustering and Sparse PCA. In Advances in Neural Information Processing Systems (NIPS), pages 847–855, 2010.
[12] M. Hein and S. Setzer. Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts. In Advances in Neural Information Processing Systems (NIPS), 2011.
[13] E. Merkurjev, T. Kostic, and A. Bertozzi. An mbo scheme on graphs for segmentation and image processing. UCLA CAM Report 12-46, 2012.
[14] C. Michelot. A Finite Algorithm for Finding the Projection of a Point onto the Canonical Simplex of Rn. Journal of Optimization Theory and Applications, 50(1):195–200, 1986.
[15] S. Rangapuram and M. Hein. Constrained 1-Spectral Clustering. In International conference on Artificial Intelligence and Statistics (AISTATS), pages 1143–1151, 2012.
[16] J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22(8):888–905, 2000.
[17] A. Szlam and X. Bresson. A total variation-based graph clustering algorithm for cheeger ratio cuts. UCLA CAM Report 09-68, 2009.
[18] A. Szlam and X. Bresson. Total variation and cheeger cuts. In International Conference on Machine Learning (ICML), pages 1039–1046, 2010.
[19] Zhirong Yang, Tele Hao, Onur Dikmen, Xi Chen, and Erkki Oja. Clustering by nonnegative matrix factorization using graph random walk. In Advances in Neural Information Processing Systems (NIPS), pages 1088–1096, 2012.
[20] Zhirong Yang and Erkki Oja. Clustering by low-rank doubly stochastic matrix decomposition. In International Conference on Machine Learning (ICML), 2012. 9