RUI: Embeddings of Discrete Metric Spaces into Banach Spaces

RUI:将离散度量空间嵌入 Banach 空间

基本信息

  • 批准号:
    1700176
  • 负责人:
  • 金额:
    $ 17.8万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2017
  • 资助国家:
    美国
  • 起止时间:
    2017-07-01 至 2021-06-30
  • 项目状态:
    已结题

项目摘要

This project deals with embeddings of finite sets into spaces with well-understood geometry. Such embeddings form a well-established tool in theoretical computer science. Their usefulness can be seen in the following example: Analysis of large sets of data is important in many contexts. Usually data is endowed with a natural distance (degree of dissimilarity) of its elements. One of the useful approaches to analysis of such sets of data is to use some low-distortion embeddings of the set into a space whose structure is well-known, for example into a two-dimensional or three-dimensional space. One can subsequently employ algorithms available in computational geometry and tools from classical mathematics. In some cases one can even visualize the structure of the set, for example, see its clusters. Another application of embeddings is to construction of approximate algorithms in cases where the algorithms for finding the exact solution of a combinatorial optimization problem are not practical (consume too much time) and we seek not necessarily the optimal solution, but a solution that is close (in some sense) to being optimal. In many cases the best known approximate algorithms are based on metric embeddings. The project aims to deepen understanding in this important area.The main goal of the proposal is to study embeddings of discrete metric spaces into Banach spaces. The existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts, for example for applications in topology, weaker types of embeddings are useful, and even embeddings into high-dimensional or infinite-dimensional Banach spaces lead to important insights. This project will contribute to the following general question: Find new classes of embeddings of finite and locally finite metric spaces into Banach spaces and find new types of obstructions to such embeddings. The three main directions of the work are: (1) determine to what extent expanders and graphs with large girth resist nontrivially good embeddings; (2) find characterizations of well-known classes of Banach spaces in terms of embeddings; and (3) analyze structures that create obstructions to coarse embeddings of spaces with bounded geometry into a Hilbert space. The project is expected to employ a mixture of methods of geometric functional analysis and graph theory, with some use of methods of probability theory and geometric group theory.
这个项目涉及有限集合嵌入到具有良好理解的几何空间中。这种嵌入形成了理论计算机科学中的一个完善的工具。它们的有用性可以从下面的例子中看出:分析大量数据集在许多情况下都很重要。通常,数据被赋予其元素的自然距离(相异度)。分析这些数据集的有用方法之一是使用该集合的一些低失真嵌入到其结构众所周知的空间中,例如嵌入到二维或三维空间中。随后可以采用计算几何中可用的算法和经典数学中的工具。在某些情况下,甚至可以可视化集合的结构,例如,查看其集群。 嵌入的另一个应用是在寻找组合优化问题的精确解的算法不实用(消耗太多时间)的情况下构造近似算法,并且我们不一定要寻求最优解,而是寻求接近(在某种意义上)最优的解。在许多情况下,最著名的近似算法是基于度量嵌入。该项目旨在加深对这一重要领域的理解。该提案的主要目标是研究离散度量空间到Banach空间的嵌入。在实际应用中,低失真嵌入到平面中的情况相当少见。在许多情况下,例如在拓扑学中的应用,较弱类型的嵌入是有用的,甚至嵌入到高维或无限维Banach空间中也会产生重要的见解。这个项目将有助于以下一般性问题:找到新的类嵌入的有限和局部有限度量空间到Banach空间,并找到新的类型的障碍,这样的嵌入。工作的三个主要方向是:(1)确定在多大程度上具有大围长的扩张器和图抵抗非平凡的好嵌入;(2)找到著名的Banach空间类的嵌入特征;(3)分析结构,这些结构对有界几何空间到希尔伯特空间的粗嵌入造成障碍。该项目预计将采用几何函数分析和图论的混合方法,并使用一些概率论和几何群论的方法。

项目成果

期刊论文数量(10)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Images of nowhere differentiable Lipschitz maps of $[0,1]$ into $L_1[0,1]$
无处可微的 Lipschitz 图像将 $[0,1]$ 映射到 $L_1[0,1]$
  • DOI:
    10.4064/fm493-12-2017
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0.6
  • 作者:
    Catrina, Florin;Ostrovskii, Mikhail I.
  • 通讯作者:
    Ostrovskii, Mikhail I.
On embeddings of locally finite metric spaces into ℓ
将局部有限度量空间嵌入到
Bourgain discretization using Lebesgue-Bochner spaces
使用 Lebesgue-Bochner 空间进行布尔干离散化
  • DOI:
    10.2989/16073606.2019.1605414
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0.7
  • 作者:
    Ostrovskii, Mikhail I.;Randrianantoanina, Beata
  • 通讯作者:
    Randrianantoanina, Beata
Lipschitz-free Spaces on Finite Metric Spaces
有限度量空间上的利普希茨自由空间
  • DOI:
    10.4153/s0008414x19000087
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Dilworth, Stephen J.;Kutzarova, Denka;Ostrovskii, Mikhail I.
  • 通讯作者:
    Ostrovskii, Mikhail I.
Generalized Transportation Cost Spaces
广义运输成本空间
  • DOI:
    10.1007/s00009-019-1433-8
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Ostrovska, Sofiya;Ostrovskii, Mikhail I.
  • 通讯作者:
    Ostrovskii, Mikhail I.
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Mikhail Ostrovskii其他文献

Mikhail Ostrovskii的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Mikhail Ostrovskii', 18)}}的其他基金

RUI: Embeddings of Discrete Metric Spaces into Banach Spaces
RUI:将离散度量空间嵌入 Banach 空间
  • 批准号:
    1953773
  • 财政年份:
    2020
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Standard Grant
RUI: Embeddings of discrete metric spaces into Banach spaces
RUI:将离散度量空间嵌入到 Banach 空间中
  • 批准号:
    1201269
  • 财政年份:
    2012
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Standard Grant

相似海外基金

Language Embeddings for Proof Engineering
用于证明工程的语言嵌入
  • 批准号:
    EP/Y000242/1
  • 财政年份:
    2023
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Research Grant
REU Site: Beyond Language: Training to Create and Share Vector Embeddings across Applications
REU 网站:超越语言:跨应用程序创建和共享向量嵌入的培训
  • 批准号:
    2244259
  • 财政年份:
    2023
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Standard Grant
Learning explanable embeddings for topics and its applications
学习主题及其应用的可解释嵌入
  • 批准号:
    23K11231
  • 财政年份:
    2023
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
CAREER: Unified Reference-Free Early Detection of Hardware Trojans via Knowledge Graph Embeddings
职业:通过知识图嵌入对硬件木马进行统一的无参考早期检测
  • 批准号:
    2238976
  • 财政年份:
    2023
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Continuing Grant
Collaborative Research: Image-based Readouts of Cellular State using Universal Morphology Embeddings
协作研究:使用通用形态学嵌入基于图像的细胞状态读出
  • 批准号:
    2348683
  • 财政年份:
    2023
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Standard Grant
Next Generation Psychological Embeddings
下一代心理嵌入
  • 批准号:
    ES/W007347/1
  • 财政年份:
    2022
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Research Grant
Pursuit-Evasion Games on Graph Embeddings
图嵌入上的追逃游戏
  • 批准号:
    575368-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Master's
Collaborative Research: Image-based Readouts of Cellular State using Universal Morphology Embeddings
协作研究:使用通用形态学嵌入基于图像的细胞状态读数
  • 批准号:
    2134695
  • 财政年份:
    2022
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Standard Grant
Collaborative Research: Image-based Readouts of Cellular State using Universal Morphology Embeddings
协作研究:使用通用形态学嵌入基于图像的细胞状态读出
  • 批准号:
    2134696
  • 财政年份:
    2022
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Standard Grant
2-Cell Embeddings of Graphs
图的 2 单元嵌入
  • 批准号:
    559667-2021
  • 财政年份:
    2022
  • 资助金额:
    $ 17.8万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Doctoral
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了