A Polynomial Time Algorithm for Rayleigh Ratio on Discrete Variables: Replacing Spectral Techniques for Expander Ratio, Normalized Cut, and Cheeger Constant

Dorit S. Hochbaum ()
Additional contact information
Dorit S. Hochbaum: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720

Operations Research, 2013, vol. 61, issue 1, 184-198

Abstract: A general form of minimizing the Rayleigh ratio on discrete variables is shown here, for the first time, to be polynomial time solvable. This is significant because major problems in clustering, partitioning, and imaging can be presented as the Rayleigh ratio minimization on discrete variables and an orthogonality constraint. These challenging problems are modeled as the normalized cut problem, the graph expander ratio problem, the Cheeger constant problem, or the conductance problem, all of which are NP-hard. These problems have traditionally been solved, heuristically, using the “spectral technique.” A unified framework is provided here whereby all these problems are formulated as a constrained minimization form of a quadratic ratio, referred to here as the Rayleigh ratio . The quadratic ratio is to be minimized on discrete variables and a single sum constraint that we call the balance or orthogonality constraint. When the discreteness constraints on the variables are disregarded, the resulting continuous relaxation is solved by the spectral method. It is shown here that the Rayleigh ratio minimization subject to the discreteness constraints requiring each variable to assume one of two values in {- b ,1} is solvable in strongly polynomial time, equivalent to a single minimum s , t cut algorithm on a graph of same size as the input graph, for any nonnegative value of b . This discrete form for the Rayleigh ratio problem was often assumed to be NP-hard. Not only is it shown here that the discrete Rayleigh ratio problem is polynomial time solvable, but also the algorithm is more efficient than the spectral algorithm. Furthermore, an experimental study demonstrates that the new algorithm provides in practice an improvement, often dramatic, on the quality of the results of the spectral method, both in terms of approximating the true optimum of the Rayleigh ratio problem on both the discrete variables and the balance constraint, and in terms of the subjective partition quality. A further contribution here is the introduction of a problem, the quantity-normalized cut , generalizing all the Rayleigh ratio problems. The discrete version of that problem is also solved with the efficient algorithm presented. This problem is shown, in a companion paper, to enable the modeling of features essential to clustering that are valuable in practical applications.

Keywords: Cheeger constant; parametric cut algorithm; Fiedler eigenvector; quantity-normalized cut (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1126 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:1:p:184-198

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().