Material Detail

Convex transduction with the normalized cut

Convex transduction with the normalized cut

This video was recorded at Workshop on Machine Learning, SVM and Large Scale Optimization, Thurnau 2005. We discuss approaches to transduction based on graph cut cost functions. More specifically, we focus on the normalized cut, which is the cost function of choice in many clustering applications, notably in image segmentation. Since optimizing the normalized cut cost is an NP-complete problem, much of the research attention so far has gone to relaxing the problem of normalized cut clustering to tractable problems, producing so far a spectral relaxation and a more recently a tighter but computationally much tougher semi-definite programming (SDP) relaxation. In this paper we deliver two main contributions: first, we show how an alternative SDP relaxation yields a much more tractable... Show More


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.