Optimization Techniques for Geometrizing Real-World Data

现实世界数据几何化的优化技术

• 批准号: 1913134
• 负责人: Soledad Villar
• 金额: $ 5.06万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-01 至 2020-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1913134&HistoricalAwards=false
• 关键词: Optimization; Techniques; Geometrizing; Real; World

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.

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