Normalized Cuts has successfully been applied to a wide range of tasks in computer vision, it is indisputably one of the most popular segmentation algorithms in use today. A number of extensions to this approach have also been proposed, ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. It was recently shown how a general linearly constrained Normalized Cut problem can be solved. This was done by proving that strong duality holds for the Lagrangian relaxation of such problems. This provides a principled way to perform multi-class partitioning while enforcing any linear constraints exactly.
The Lagrangian relaxation requires the maximization of the algebraically smallest eigenvalue over a one-dimensional matrix sub-space. This is an unconstrained, piece-wise differentiable and concave problem. In this paper we show how to solve this optimization efficiently even for very large-scale problems. The method has been tested on real data with convincing results.
Efficiently Solving the Fractional Trust Region Problem
Asian Conference on Computer Vision ; 2007 ; Tokyo, Japan November 18, 2007 - November 22, 2007
2007-01-01
10 pages
Article/Chapter (Book)
Electronic Resource
English
Golden Section , Linear Constraint , Subgradient Method , Lagrangian Relaxation , Dual Problem Pattern Recognition , Artificial Intelligence , Algorithm Analysis and Problem Complexity , Computer Science , Biometrics , Image Processing and Computer Vision , Computer Imaging, Vision, Pattern Recognition and Graphics
Solving Structured Multifacility Location Problems Efficiently
Online Contents | 1994
|Solving the trust issue for neural nets
Online Contents | 2017
Springer Verlag | 2022
|