Optimization Techniques for Geometrizing Real-World Data

数据是科学领域、政府和私营企业的共同标准。在过去的几十年里，能够利用数据来发现模式已经产生了科学突破，并改变了商业范式。该项目侧重于针对特定数据科学问题的数学和算法技术，针对当前相关的领域问题、技术和数据量进行定制。我们考虑的理论问题是(i)聚类（本质上是根据无监督方式的相似性对数据进行分组），（ii）降维（在保留相关特征的同时减少数据量），以及（iii）二次分配（找到不同数据集之间的对应关系）。我们在这个项目中考虑的主要潜在应用是计算生物学，特别是单细胞测序数据的处理。单细胞测序技术是最近才发展起来的，而且正在迅速改进，产生了新的数据集、问题和挑战，从数学的角度来看，这些数据集、问题和挑战都很有趣，并且具有潜在的巨大影响。该项目将有数学家与计算生物学家密切合作，目标是识别科学领域中发生的数据科学问题，并开发适当的算法和数学工具。给定单细胞基因表达数据，表明每个基因在每个细胞中表达的次数，一个目标是选择几个可用于识别不同类型细胞的基因。这个问题在计算生物学文献中被称为遗传标记选择。在第一种方法中，我们假设每个细胞的类别是已知的，并且问题可以作为监督降维。我们将其建模为投影因子恢复问题，并使用半定规划和线性规划等优化工具进行求解。目标是双重的，我们的目标是研究我们设计的模型的数学性质，并开发一个有效的工具供从业者使用。该项目的第二阶段是使问题无监督，因此聚类将是一个基本步骤。我们将研究聚类方法的稳定性，并基于统计和优化技术提供一种有效的算法来评估聚类的质量。这个工具的潜在用途是一般的数据科学，而不仅仅是基因表达数据集。最后，第三个目标是对齐来自不同实验的数据集。这个问题在数据科学中普遍存在，图匹配和形状匹配是一些特殊的例子。在计算生物学的背景下，排列问题被称为批校正，它可以用最优运输或二次分配问题来建模。我们将开发对齐算法，并研究它们在不同数据模型下的收敛和恢复特性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Data is a common denominator to scientific fields, governments, and private enterprises. Being able to exploit data to find patterns has produced scientific breakthroughs and shifted business paradigms in the last several decades. This project focuses on mathematical and algorithmic techniques for specific data science problems, tailored to currently relevant domain problems, technologies, and volumes of data. The theoretical problems we consider are (i) clustering (which essentially consists on grouping data according to similarity in an unsupervised way), (ii) dimensionality reduction (reducing the volume of the data while preserving its relevant features), and (iii) quadratic assignment (finding correspondences between different datasets). The main underlying application we consider in this project is computational biology, in particular the processing of single-cell sequencing data. The technology for single-cell sequencing has been very recently developed and it is improving quickly, producing new datasets, problems and challenges that are interesting from a mathematical point of view and have potentially enormous impact. The project will have mathematicians working closely to computational biologists with the goal of identifying data science problems occurring in the scientific domain and to develop appropriate algorithms and mathematical tools.Given single-cell genetic expression data indicating how many times each gene is expressed in each cell, one objective is to select a few genes that can be used to identify different classes of cells. This problem is known in the computational biology literature as genetic marker selection. In a first approach we assume the class of each cell is known and the problem can be posed as supervised dimensionality reduction. We model it as a projection factor recovery problem, and we approach it using optimization tools such as semidefinite and linear programming. The objective is two-fold, we aim to study mathematical properties of the model we devise, and to develop an efficient tool to be used by practitioners. A second stage of the project is to make the problem unsupervised, therefore clustering will be a fundamental step. We will study stability properties of clustering methods and we will provide an efficient algorithm to evaluate the quality of clusters, based on statistical and optimization techniques. The potential use of this tool is general to data science and not just gene expression datasets. Finally, a third objective is to align datasets coming from different experiments. This problem is ubiquitous in data science, with graph matching and shape matching as some particular cases. In the context of computational biology the alignment problem is known as batch correction and it can be modeled with optimal transport or as a quadratic assignment problem. We will develop alignment algorithms and study their convergence and recovery properties under different data models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.