Optimization Techniques for Geometrizing Real-World Data

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

• 批准号: 2044349
• 负责人: Soledad Villar
• 金额: $ 2.82万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-06-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2044349&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的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响来通过评估来支持的。

项目成果

Cibercoloquio latinoamericano de matemáticas

拉丁美洲数学论坛

• 发表时间: 2021
• 期刊: Notices of the American Mathematical Society
• 作者: Campos, D;Rivera, M;Salazar, MA;Samper, JA;Simental, J;Villar, S
• 通讯作者: Villar, S

Fitting Very Flexible Models: Linear Regression With Large Numbers of Parameters

拟合非常灵活的模型：具有大量参数的线性回归

• DOI: 10.1088/1538-3873/ac20ac
• 发表时间: 2021
• 期刊: Publications of the Astronomical Society of the Pacific
• 影响因子: 3.5
• 作者: Hogg, David W.;Villar, Soledad
• 通讯作者: Villar, Soledad

A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants

• DOI: 10.1109/icassp39728.2021.9413523
• 发表时间: 2021-06
• 期刊: ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 作者: Ningyuan Huang;Soledad Villar

SqueezeFit: Label-Aware Dimensionality Reduction by Semidefinite Programming

• DOI: 10.1109/tit.2019.2962681
• 发表时间: 2020-06-01
• 期刊: IEEE TRANSACTIONS ON INFORMATION THEORY
• 影响因子: 2.5
• 作者: McWhirter, Culver;Mixon, Dustin G.;Villar, Soledad
• 通讯作者: Villar, Soledad

Experimental performance of graph neural networks on random instances of max-cut

• DOI: 10.1117/12.2529608
• 发表时间: 2019-08
• 作者: Weichi Yao;A. Bandeira;Soledad Villar