Numerical Methods for Nonlinear Partial Differential Equations, with applications to Optimal Transportation, and Geometric Data Reduction

非线性偏微分方程的数值方法，及其在最优运输和几何数据简化中的应用

• 批准号: RGPIN-2016-03922
• 负责人: Oberman, Adam
• 金额: $ 2.4万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708704
• 关键词: Numerical; Methods; Nonlinear; Partial; Differential

A fundamental change is taking place in the role of applied and computational mathematics. Across science, technology, commerce, and medicine our ability to collect and store data is increasing dramatically. These developments call for a change in our understanding of data and demand the development of new tools. The techniques of computational mathematics are uniquely suited for building these tools. I propose to build new algorithms for large data sets and apply these algorithms to solve important real-world problems. The primary objectives are to: 1. Develop an extension of my algorithm for solving the Optimal Transportation (OT) problem. One of the fundamental tools of mathematics is impose a metric structure on complex sets. The Wasserstein distance does so for the set of probability measures. However, evaluating this distance is not given explicitly: it is obtained as the solution of an infinite dimensional variational problem, the Optimal Transportation problem. Building good methods for solving this problem allow this distance to be computed. 2. Develop an algorithm for data reduction using extremal points. Given a scatterplot of two dimensional points, the extremal values are the farthest out from the centre. Mathematically, the convex hull is used to represent the extremal values. There are already algorithms for finding convex hulls, but they break down when the number of points, or the dimension of the points, is too large. The proposed research will develop algorithms to find extremal points of large set of high dimensional data. 3. Develop an algorithm, Multidimensional Quicksort, for anomaly detection. You may perform anomaly detection when you check your monthly credit card bill. For example, looking for items that are unusual, either because of the amount charged, or because the vendor is not recognized. The proposed research will develop algorithms to perform anomaly detection on huge amounts of data very quickly. The data is simplified by using a density function, which represents the pattern of the types of anomalies we are looking for. The process of sorting the points is replaced by solving an equation involving the density function. Once we have the solution of the equation, we can use it to quickly find the anomalies. 4. Continue foundational work building of nonlinear Partial Differential Equation (PDE) solvers. The corresponding expected outcomes include: 1.(a) An effective method to compare documents or images. (b) A geometry-sensitive method to perform registration of shapes or images. (c) A state-of-the-art image warping tool, to be used by several top surgeons at US hospitals. 2.(a) A data reduction tool for finding extreme values of high dimensional data. (b) Improved off-line and potential real-time performance monitoring for helicopters. 3. Streaming detection of stock anomalies. 4. Effective solvers for new equations, leading to future outcomes like 1-3 above.

应用数学和计算数学的作用正在发生根本性的变化。 在科学、技术、商业和医学领域，我们收集和存储数据的能力正在急剧增强。这些发展要求我们改变对数据的理解，并需要开发新工具。计算数学技术特别适合构建这些工具。 我建议为大数据集构建新算法，并应用这些算法来解决重要的现实问题。主要目标是： 1. 开发我的算法的扩展来解决最佳运输 (OT) 问题。数学的基本工具之一是将度量结构强加于复杂的集合上。 Wasserstein 距离对概率度量集执行此操作。 然而，没有明确给出对该距离的评估：它是作为无限维变分问题（最优运输问题）的解而获得的。 建立解决该问题的良好方法可以计算该距离。 2. 开发一种使用极值点进行数据缩减的算法。给定二维点的散点图，极值是距中心最远的值。在数学上，凸包用于表示极值。已经有寻找凸包的算法，但是当点的数量或点的维度太大时，它们就会崩溃。拟议的研究将开发算法来查找大量高维数据的极值点。 3. 开发一种用于异常检测的算法，多维快速排序。您可以在检查每月信用卡账单时执行异常检测。例如，寻找不寻常的物品，要么是因为收费金额，要么是因为供应商不被认可。拟议的研究将开发算法来非常快速地对大量数据执行异常检测。通过使用密度函数来简化数据，密度函数代表我们正在寻找的异常类型的模式。对点进行排序的过程被求解涉及密度函数的方程所取代。一旦我们得到了方程的解，我们就可以用它来快速找到异常现象。 4. 继续建立非线性偏微分方程 (PDE) 求解器的基础工作。 相应的预期成果包括： 1.(a) 比较文档或图像的有效方法。 (b) 一种几何敏感方法，用于执行形状或图像的配准。 (c) 最先进的图像变形工具，将由美国医院的几位顶级外科医生使用。 2.(a) 一种用于查找高维数据极值的数据缩减工具。 (b) 改进直升机的离线和潜在实时性能监测。 3.库存异常的流式检测。 4. 新方程的有效求解器，导致未来的结果，如上面的 1-3。