M.Sc Thesis
M.Sc Student Feld Tal Michael NonLinear Spectral Analysis for Grouping Problems Department of Electrical Engineering Professor Guy Gilboa Dr. Noam Kaplan

Abstract

Perceptual grouping problems in vision can often be reformulated as balanced partitioning of a graph, in which every object is a node in the graph and similarities between objects are the edge weights. Although NP-hard, balanced partitioning is usually relaxed to the minimization of a corresponding energy, which under weaker conditions is equivalent to a balanced criteria. The current leading balanced criterion - the Cheeger cut, corresponds to the minimization of the Total variation over the L1 norm, which is a particular case of a Rayleigh quotient of two absolutely one-homogeneous functionals. We examine the problem of minimizing generalized Rayleigh quotients of the form J(u)/H(u), where both J and H are absolutely one-homogeneous functionals. This can be viewed as minimizing J where the solution is constrained to be on a generalized sphere with H(u) = 1, where H is any norm or semi-norm. The solution admits a nonlinear eigenvalue problem, based on the subgradients of J and H. We examine several flows which minimize the ratio. This is done both by time-continuous flow formulations and by discrete iterations. We focus on a certain flow, which is easier to analyze theoretically, following the theory of Brezis on flows with maximal monotone operators. A comprehensive theory is established, including convergence of the flow. We then turn into a more specific case of minimizing graph total variation on the L1 sphere, which approximates the Cheeger-cut problem. Experimental results show the applicability of such algorithms for clustering and classification of images. Finally, we propose a multi-class version of our flow that generates statistically independent binary eigenfunctions. We motivate the use of this set of eigenfunctions by presenting a new reformulation of the spectral hashing problem which is experimentally tested as well.