Nonlinear Eigenproblems in Data Analysis - Balanced Graph Cuts and the RatioDCA-Prox
This work addresses graph partitioning challenges in data analysis, offering incremental improvements to existing algorithms for balanced cuts.
The paper tackles the problem of computing balanced graph cuts by relaxing them into nonlinear eigenproblems, proposing a family of algorithms that generalize previous methods and analyzing their convergence properties.
It has been recently shown that a large class of balanced graph cuts allows for an exact relaxation into a nonlinear eigenproblem. We review briefly some of these results and propose a family of algorithms to compute nonlinear eigenvectors which encompasses previous work as special cases. We provide a detailed analysis of the properties and the convergence behavior of these algorithms and then discuss their application in the area of balanced graph cuts.