|Title: ||Efficiently Solving the Fractional Trust Region Problem|
|Fulltext:|| PDF PS|
|Authors: ||Eriksson, Anders and Olsson, Carl and Kahl, Fredrik|
|Document Type:||Conference Paper|
|Conference: ||Asian Conference on Computer Vision|
|Conference location: ||Tokyo, Japan|
|Status: ||In Press|
|Abstract: ||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