| Home of MIG Publications |
| Title: | Efficiently Solving the Fractional Trust Region Problem |
|---|---|
| Fulltext: | PDF PS |
| Authors: | Eriksson, Anders and Olsson, Carl and Kahl, Fredrik |
| Year: | 2007 |
| Document Type: | Conference Paper |
| Conference: | Asian Conference on Computer Vision |
| Conference location: | Tokyo, Japan |
| Status: | In Press |
| Refereed: | Yes |
| 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 convincing results. |
| BibTex item: | BibTex |