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.
Copyright. All Rights Reserved.