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

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

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.