FINC: An Efficient and Effective Optimization Method for Normalized Cut

Xiaojun Chen, Zhicong Xiao, Feiping Nie, Joshua Zhexue Huang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

The optimization methods for solving the normalized cut model usually involve three steps, i.e., problem relaxation, problem solving and post-processing. However, these methods are problematic in both performance since they do not directly solve the original problem, and efficiency since they usually depend on the time-consuming eigendecomposition and k-means (or spectral rotation) for post-processing. In this paper, we propose a fast optimization method to speedup the classical normalized cut clustering process, in which an auxiliary variable is introduced and alternatively updated along with the cluster indicator matrix. The new method is faster than the conventional three-step optimization methods since it solves the normalized cut problem in one step. Theoretical analysis reveals that the new method is able to monotonically decrease the normalized cut objective function and converge in finite iterations. Moreover, we have proposed efficient methods for adjust two regularization parameters. Extensive experimental results show the superior performance of the new method. Moreover, it is faster than the existing methods for solving the normalized cut.

Keywords

  • Clustering
  • Clustering algorithms
  • Clustering methods
  • graph cut
  • Iterative methods
  • Laplace equations
  • Linear programming
  • normalized cut
  • Optimization methods
  • Problem-solving
  • spectral clustering
  • spectral methods

Fingerprint

Dive into the research topics of 'FINC: An Efficient and Effective Optimization Method for Normalized Cut'. Together they form a unique fingerprint.

Cite this