Extreme-scale algorithms for geometric graphical data models in imaging, social and network science

大数据现在很重要；极致规模的硬件、编程模型和存储解决方案正在开发中。然而，需要解决转换算法和大数据集之间的联系。研究人员经常谈论即将到来的“大数据问题”，但却略过能够真正以具体方式解决问题的相关算法，这通常是因为传统的数据分析方法在高性能计算(HPC)领域并不普遍，而且HPC的专业知识在数据领域也并不普遍。该项目将巩固这种联系，通过可识别的具体算法研究来解决问题，并在最新的硬件平台上实施这些方法，从而使“大数据”问题成为现实。最近，首席研究人员开发了可扩展的桌面算法，利用快速频谱解算器来计算大数据稀疏分类问题的解决方案，从而弥补了这一差距。该项目将建立在这些可伸缩算法的基础上，以在几个大型平台上实施它们，并将解决桌面计算不足的重要应用领域。该项目的应用领域包括化学和生物毒剂的高维高光谱视频数据、对国土安全具有重要意义的问题、时空多模式犯罪数据的统计分析以及大规模社会网络分析。该项目重点介绍一类新的数据聚类算法，该算法旨在解决图上最小割集问题的变体，用于大数据应用，如高光谱视频数据分析、时空多模式犯罪数据的统计分析和大规模社会网络分析。半监督和无监督机器学习问题被包括在所考虑的问题类别中。图最小割问题等价于图上的全变差最小化问题，是机器学习应用中的一种常用模型，但计算复杂。基于漫射界面和动态阈值等思想，该项目最初是为物理科学模型开发的，随后转移到低维图像处理应用程序，该项目将开发利用可伸缩光谱图算法的最新进展来解决真正的图割问题的方法。这些方法的新代码将被开发用于大型并行体系结构。这一研究将推进算法的理论问题和应用领域。

Big data is important right now; and extreme scale hardware, programming models and storage solutions are being developed. However the connection between transformational algorithms and the big data sets needs to be addressed. Researchers talk often about the upcoming "big data problem," yet skim over the relevant algorithms that can truly attack the problems in a concrete fashion, often because the traditional means of data analysis are not prevalent in the high-performance computing (HPC) world, and in concert, the HPC expertise is not prevalent in the data world. This project will solidify this connection, making the "big data" problem real by attacking the issues through identifiable concrete algorithmic research and by implementing the methods on the latest hardware platforms. Recently the principal investigator has developed scalable desktop algorithms that bridge that gap, leveraging fast spectral solvers to compute solutions of sparse classification problems for big data. This project will build on these scalable algorithms to implement them on several large-scale platforms and will address important application areas, for which desktop computing is insufficient. Examples of application areas for this project include high dimensional hyperspectral video data for chemical and biological agents, a problem of importance to homeland security, and statistical analysis of spatio-temporal multimodal crime data, and large-scale social network analysis.This project focuses on a new class of data-clustering algorithms that are designed to solve variants of the minimum cut problem on graphs for big data applications such as hyperspectral video data analysis, statistical analysis of spatio-temporal multimodal crime data, and large-scale social network analysis. Semi-supervised and unsupervised machine learning problems are included in the class of problems considered. The graph mincut problem is equivalent to total variation minimization on a graph and is a popular model for machine learning applications, except for its computational complexity. Building on ideas such as diffuse interfaces and dynamic thresholding, originally developed for physical sciences models and subsequently transferred to low dimensional image processing applications, this project will develop methods to solve the true graph cut problem by leveraging recent advances in scalable spectral graph algorithms. New codes for these methods will be developed for large parallel architectures. The research will advance both theoretical algorithmic issues and application areas.