CAREER: Geometric Frontiers in Algorithm Design

职业：算法设计中的几何前沿

• 批准号: 1758578
• 负责人: Anastasios Sidiropoulos
• 金额: $ 37.81万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-16 至 2021-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1758578&HistoricalAwards=false
• 关键词: CAREER; Geometric; Frontiers; Algorithm; Design

Complex data sets arise in a plethora of application domains from measurements of various physical processes, history of financial transactions, logs of user activity in a network, and so on. The analysis of such data sets is therefore a task of increasing importance for science and engineering. Even though in many applications there is an abundance of such raw inputs, extracting meaningful information can often be a major computational challenge. In most cases, this difficulty is due to the lack of a useful representation of the data.Over the recent years, geometric methods have become an indispensable tool for overcoming this difficulty. The reason behind this development is the fact that a data set endowed with pairwise similarities can be naturally interpreted as a geometric space. Such data sets include DNA sequences, statistical distributions, collections of news articles, and so on. Under this interpretation, several important data analytic questions can be understood as geometric computational problems. For example, the problem of classification can be expressed as geometric partitioning. Similarly, the problem of fitting a model to set of measurements can be thought of as interpolation in some appropriate geometric space.In these contexts, the main algorithmic challenges occur in high-dimensional, or more generally, complex metric spaces. This project aims at resolving some of the main problems inherent in the analysis of such geometric data sets, and thus enabling improved solutions for a variety of computational tasks. The project also seeks to use diverse mathematical tools in the setting of geometric data analysis, forging new connections between mathematics and computer science.The proposed research will be part of the PI's curriculum development, undergraduate and graduate teaching, and educational and outreach activities. It will also provide the set of research problems that will be used for mentoring undergraduate and graduate students.

复杂的数据集来自多种物理过程，金融交易的历史，网络中用户活动日志等的大量应用域中出现。因此，对此类数据集的分析是提高对科学和工程的重要性的任务。即使在许多应用中，这种原始输入有很多，但提取有意义的信息通常可能是一个主要的计算挑战。在大多数情况下，这种困难是由于缺乏数据的有用表示。从近年来，几何方法已成为克服这一难度的必不可少的工具。这种发展背后的原因是，具有成对相似性的数据集可以自然解释为几何空间。此类数据集包括DNA序列，统计分布，新闻文章的集合等。在这种解释下，几个重要的数据分析问题可以理解为几何计算问题。例如，分类问题可以表示为几何分区。同样，将模型拟合到一组测量值的问题可以被认为是在某些适当的几何空间中的插值。在这些情况下，主要算法挑战发生在高维或更普遍的复杂度量空间中。该项目旨在解决分析此类几何数据集的一些主要问题，从而为各种计算任务提供了改进的解决方案。该项目还试图在几何数据分析的设置中使用多种数学工具，在数学和计算机科学之间建立新的联系。拟议的研究将成为PI课程开发，本科和研究生教学以及教育和外展活动的一部分。它还将提供一组研究问题，这些问题将用于指导本科生和研究生。