Nonlinear Eigenproblems and Tight Relaxations of Constrained Fractional Set Programs

Matthias Hein
Saarland University
Computer Science

It turns out that many problems in data analysis and beyond have natural formulations as nonlinear eigenproblems. In this talk I present our recent line of research in this area. This includes the efficient computation of nonlinear eigenvectors via a generalization of the inverse power method and a general result showing that a certain class of NP-hard combinatorial problems such as balanced graph cuts have tight relaxations into nonlinear eigenproblems. In the case of the Cheeger cut this corresponds to the second eigenvector of the p-graph Laplacian for p=1. A generalization of this result to constrained fractional set programs with applications in local clustering and community detection will be discussed. Empirically, we outperform loose spectral/convex relaxations often by large margin.

Back to Convex Relaxation Methods for Geometric Problems in Scientific Computing