The proposed activity is to develop and analyze new computational methods for a graph partitioning problem based on the Beltrami energy. This problem has diverse applications in machine learning and image analysis (medical, satellite, and material). For example, a clear need for such methods in imaging has been identified by collaborators at the California NanoSystems Institute, where the proposed work will directly impact fundamental research in nano science and foster the understanding of amyloid beta sheets. Such amyloids are associated with the pathology of more than 20 serious human diseases including Alzheimer's and other neurodegenerative diseases. Thanks to the multidisciplinary nature of the activity, awareness and literacy outside one's field will also be mutually fostered for all involved parties.

The PIs, together with their students and collaborators, will seek new methods that combine variational arguments with ideas from geometry and partial differential equations in order to extend and overcome the limitations of existing methods. The research has three goals. The first goal concerns fundamental theoretical questions raised by the proposed model: analyze the existence, uniqueness, and properties of the minimizers of the variational problems; establish a generalized isoperimetric inequality related to the Beltrami functional in the continuum; and explore relations to existing theorems and conjectures about optimal partitions. A graph analogue of the Beltrami energy is formulated and is the foundation for a graph partitioning objective. The PIs have identified a relaxation of this objective and propose an in-depth study of a provably convergent rearrangement method for its solution. The second goal addresses the important computational and numerical aspects of the proposed graph partitioning model. An efficient optimization strategy is key for the framework to be usable in practical applications. Here, promising primal-dual methods from convex optimization will be utilized, as well as other competitive state-of-the-art methods. To develop the most efficient solution method, it will be crucial to explore the similarities to other models, including those for non-negative matrix factorization and those related to motion by mean curvature. The third goal is to address concrete, real-world problems and to engage the developed algorithms in practical applications of societal importance.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Type
Standard Grant (Standard)
Application #
1418812
Program Officer
Leland M. Jameson
Project Start
Project End
Budget Start
2014-08-15
Budget End
2014-10-31
Support Year
Fiscal Year
2014
Total Cost
$79,000
Indirect Cost
Name
University of California Los Angeles
Department
Type
DUNS #
City
Los Angeles
State
CA
Country
United States
Zip Code
90095