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.