Geometric Methods for Graph Partitioning

拟议的活动是开发和分析基于Beltrami能量的图划分问题的新计算方法。这个问题在机器学习和图像分析（医学，卫星和材料）中有不同的应用。例如，加州纳米系统研究所的合作者已经确定了成像中对这种方法的明确需求，在那里，拟议的工作将直接影响纳米科学的基础研究，并促进对淀粉样蛋白β片层的理解。这种淀粉样蛋白与20多种严重的人类疾病的病理学有关，包括阿尔茨海默病和其他神经退行性疾病。由于该活动的多学科性质，所有参与方的认识和素养也将相互促进。PI及其学生和合作者将寻求新的方法，将联合收割机变分论点与几何和偏微分方程的思想相结合，以扩展和克服现有方法的局限性。这项研究有三个目标。第一个目标涉及的基本理论问题所提出的模型：分析的存在性，唯一性，和性质的变分问题的最小值;建立一个广义等周不等式相关的Beltrami功能在连续体;并探讨现有的定理和最优分割的关系。一个图形模拟的贝尔特拉米能源制定和图形分割目标的基础。PI已经确定了这个目标的放松，并提出了一个可证明收敛的重排方法，其解决方案的深入研究。第二个目标是解决所提出的图划分模型的重要计算和数值方面。一个有效的优化策略是框架在实际应用中可用的关键。在这里，将利用凸优化的有前途的原始-对偶方法，以及其他有竞争力的最先进的方法。为了开发最有效的求解方法，探索与其他模型的相似性至关重要，包括非负矩阵分解和与平均曲率运动相关的模型。第三个目标是解决具体的现实问题，并将开发的算法应用于具有社会重要性的实际应用中。

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.