Nonlinear partial differential equations and continuum limits for large discrete sorting problems

大型离散排序问题的非线性偏微分方程和连续极限

• 批准号: 1656030
• 负责人: Jeffrey Calder
• 金额: $ 3.71万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1656030&HistoricalAwards=false
• 关键词: Nonlinear; partial; differential; equations; continuum

The goal of this project is to study algorithms for sorting large amounts of high-dimensional data. Sorting, or ordering, data is one of the most fundamental problems in computational science, and in today's data-driven world, there is a need to develop new algorithms and tools for handling massive amounts of data in novel ways. Many sorting algorithms are computationally intensive, but have a highly predictable structure when applied to very large amounts of data. A deep mathematical understanding of this structure will lead to new insights that have the potential to significantly improve performance. Applications of sorting are ubiquitous in science and engineering, and include the analysis of DNA sequences, sorting of hits in web searches, and fingerprint identification. A significant improvement in any sorting algorithm would have a broad impact on many fields of science and engineering. This project will study two algorithms for sorting multivariate data: non-dominated sorting, and convex hull ordering. Non-dominated sorting is fundamental in multi-objective optimization, which is commonly used in scientific and engineering contexts. It has recently been shown that non-dominated sorting of random points in Euclidean space has a continuum limit that corresponds to solving a Hamilton-Jacobi equation. The first objective of this project is to study the regularity of viscosity solutions of this Hamilton-Jacobi equation, and to develop highly accurate numerical schemes for approximating its solution. The second, and main objective, is to study convex hull ordering, which is widely used in robust statistics. It is conjectured that convex hull ordering has a continuum limit that corresponds to affine invariant curvature motion. This project aims to study, and prove rigorously, this conjectured continuum limit. This result provides an asymptotic distributional theory for convex hull ordering, which is an open problem in robust statistics. Another goal of this project is to exploit this continuum limit to develop a fast algorithm for approximate convex hull ordering that can handle massive amounts of data.

该项目的目标是研究对大量高维数据进行排序的算法。数据排序是计算科学中最基本的问题之一，在当今数据驱动的世界中，需要开发新的算法和工具，以新颖的方式处理大量数据。许多排序算法都是计算密集型的，但在应用于大量数据时具有高度可预测的结构。对这种结构的深入数学理解将带来新的见解，有可能显着提高性能。排序的应用在科学和工程中无处不在，包括 DNA 序列分析、网络搜索中的命中排序以及指纹识别。任何排序算法的重大改进都会对科学和工程的许多领域产生广泛的影响。该项目将研究两种用于对多元数据进行排序的算法：非支配排序和凸包排序。非支配排序是多目标优化的基础，常用于科学和工程领域。最近的研究表明，欧几里德空间中随机点的非支配排序具有连续统极限，对应于求解 Hamilton-Jacobi 方程。该项目的第一个目标是研究 Hamilton-Jacobi 方程的粘度解的规律性，并开发高精度的数值方案来逼近其解。第二个也是主要目标是研究凸包排序，它广泛用于稳健统计。据推测，凸包排序具有对应于仿射不变曲率运动的连续统极限。该项目旨在研究并严格证明这一猜想的连续统极限。这一结果为凸包排序提供了渐近分布理论，这是鲁棒统计中的一个开放问题。该项目的另一个目标是利用这种连续统限制来开发一种可以处理大量数据的近似凸包排序的快速算法。