Oct, 2012

计算离散度度量空间的 Gromov 超伪性

PDF
TL;DR本文提出了一种通过（max，min）矩阵乘法计算固定基点的 Gromov 超半群性质的算法，可在 O (n^2.69) 的时间内确定固定基点的超半群性质，也可以在 O (n^3.69) 的时间内计算 Gromov 超半群性质并在 O (n^2.69) 的时间内找出 2 - 近似解，同时提供了一种基于 Gromov 树度量嵌入的 O (n^2) 时间复杂度的（2log_2n）逼近算法，并证明了除非存在比当前更快的（max，min）矩阵乘法算法，否则无法在 O (n^2.05) 时间内计算固定基点的超半群性质。
gromov hyperbolicityalgorithmmatrix productapproximationtree-metric embedding
发现论文，激发创造
  • 计算度量树的 Gromov-Hausdorff 距离

    本文研究度量空间之间的 Gromov-Hausdorff 距离问题，证明了对于一对树的测地度量空间，很难以小于 3 的因子近似计算该距离，同时提供了一种新的多项式时间算法，可在 O (min {n, sqrt {rn}}) 下近似计算度量树的 Gromov-Hausdorff 距离，其中 r 是两棵树中最长边长与最短边长的比率。

    Sep, 2015

  • 关于度量的 Ramsey 型现象

    研究关于有限度量空间的非线性模拟，探索其与希尔伯特空间的扭曲嵌入子空间的基数，并给出了关于嵌入和扭曲的任意精度下限和上限。

    Jun, 2004

  • 一般对称范数的近似最近邻

    每个对称赋范空间都可以采用双对数逼近的方式建立有效的最近邻搜索数据结构。我们的算法的主要技术是一个对称范数到低维度 “top-k” 范数的迭代乘积的低扭曲嵌入。同时，我们证明这些方法无法推广到一般范数。

    Nov, 2016

  • 比较模型空间的产品流形的 Gromov-Hausdorff 距离

    为了改善模型性能，最近的研究提出通过使潜空间的几何特征与基础数据结构对齐来提升机器学习模型。本文引入了一种使用 Gromov-Hausdorff 距离计算候选潜空间几何之间距离的新概念，提出了使用估计的 Gromov-Hausdorff 距离来搜索最佳潜空间几何的图搜索空间算法。本文描述了计算模型空间之间 Gromov-Hausdorff 距离的算法及其计算实现。

    Sep, 2023

  • 超度量格罗莫夫 - 瓦瑟斯坦距离

    本文研究紧致超度量空间，定义了两种超度量空间的超度量测度，探讨了它们的基本拓扑和几何性质，并且推导出了用于它们计算的多项式时间算法。

    Jan, 2021

  • 超几何嵌入的表征权衡

    该研究提出了一种嵌入树形数据结构的超 bolic embeddings 算法，无需优化即可实现任意低失真，同时提供了 h-MDS 方法来嵌入广泛的度量空间以及可处理不完整信息和可扩展的 PyTorch 实现。

    Apr, 2018

  • 度量空间中图嵌入的紧凑快速泛化误差界

    本文提出一种新的图嵌入一般化误差的上限，它作为距离表示的函数集的局部 Rademacher 复杂度的评估。我们的上限是几何半径 $R$ 的多项式，可以最快达到 $O (rac {1}{S})$，其中 $S$ 是训练数据大小。

    May, 2023

  • 随机超平面镶嵌的降维

    研究了如何利用随机超平面对区域进行均匀的镶嵌，并利用超平面将欧氏空间中的有界集嵌入哈明空间中，从而实现对欧氏空间中集合的离散化降维。

    Nov, 2011

  • 非交换格罗滕迪克问题的严密度

    证明了使用迹范数的矩阵空间中的 $L_2$ 嵌入可以得到非交换 Grothendieck 问题的近似传递性，从而说明了使用 Naor, Regev 和 Vidick 算法的近似率是最优的，并且证实了对于交换的 Little Grothendieck 问题，可以获得紧致的 NP 困难结果，这在先前是基于独特游戏猜想 (Khot 和 Naor，Mathematika 2009) 所知的。

    Dec, 2014

  • HLoOP -- 双曲空间局部异常概率

    该文章引入了一种简单框架，用于在超休克 2 空间中检测局部异常值，称为 HLoOP (Hyperbolic Local Outlier Probability)。通过在超休克空间中计算数据点到其最近邻的 Riemmanian 距离，并利用高斯概率密度函数将其与局部异常因子相结合，该方法在 WordNet 数据集上取得了令人期待的结果。

    Dec, 2023