Nov, 2023

实代数几何的覆盖数：改进的界限和应用

PDF
TL;DR我们通过证明一个上界，提出了覆盖实代数变量、多项式映射和半代数集的个数方法，该边界明显改善了 Yomdin-Comte 的最佳边界，并且证明方法更加直观。作为推论，我们的结果给出了实变量的管状邻域的内部体积边界，改进了 Lotz 和 Basu-Lerario 的结果。我们将该理论应用于三个主要的应用领域：首先，我们得到了低秩 CP 张量的覆盖数的接近最优的边界。其次，对于（一般的）多项式优化问题，我们证明了对于绘制维数的一个边界。最后，我们推导了具有有理或 ReLU 激活函数的深度神经网络的推广误差界，改进或与文献中已知的最佳结果相匹配。
发现论文，激发创造
  • 实系数代数几何中的算法：一份调查

    本文调查了实代数几何算法理论的新、旧发展，主要涵盖关于真实数的一阶理论中的量词消除和计算半代数集拓扑不变量等问题，重点分析了这些算法的复杂性和背后问题的计算难度，并对一些近年来越来越受欢迎的半定规划数值方法进行了讨论。

    Sep, 2014

  • 从样本中学习代数流形

    研究如何从一个有限数据集合中确定一个真实的代数变换，通过算法测试和 Julia 包的提供来探究拓扑和代数几何方面，包括维度，定义多项式等。

    Feb, 2018

  • 计算多项式环的线性部分：量子纠缠，张量分解和更多

    本研究讨论了如何在任意锥形多项式曲线和给定线性子空间的交集中找到元素。我们提出了一种基于多项式时间的算法来解决这个问题，并将其应用于解决低秩分解问题和量子纠缠问题等相关问题。

    Dec, 2022

  • 高秩矩阵补全的代数多样性模型

    本文以代数多样性为数据本身的情况进一步推广了低秩矩阵补全问题，结合仿射子空间集合进行研究，提出了一种有效的基于凸或非凸代价的矩阵补全算法，绕过高维幂律特征矩阵的直接处理，能够恢复合成数据和真实数据，且其性能优于传统的低秩矩阵补全和子空间聚类算法。

    Mar, 2017

  • 最小化多项式函数

    比较多元多项式函数全局优化算法，证明了使用具有半定规划的平方和松弛技术比代数方法更有效，并为实数代数几何中的广泛计算问题提供了可能性。

    Mar, 2001

  • 熵与组合维数

    通过解决 Talagrand 的熵问题，我们证明了：每个有界函数类的 L_2 覆盖数都与其 shattering 维度成指数关系。这扩展了 Dudley 关于 {0,1} 函数类的定理，对于这些函数，shattering 维度是他们的 Vapnik-Chervonenkis 维度。在凸几何中，这意味着凸体 K 的熵可以由其坐标投影中包含的固定边长的立方体的最大维度控制。该理论有很多后续影响，包括 Elton 的最优定理以及实值情况下统计中心极限定理的估计。

    Mar, 2002

  • 利用黎曼优化进行代数变种的注册

    我们研究了点云配准问题，即在不同坐标系中表示同一物体的两个点云之间寻找变换的任务。我们的方法不基于点对点的对应，而是假设并利用了数据的低维非线性几何结构。首先，我们通过在 Grassmann 流形上求解优化问题，利用代数变量逼近每个点云。然后，我们在正交群上求解优化问题，找到使两个代数变量重合的变换（旋转 + 平移）。我们使用二阶 Riemannian 优化方法来解决这两个步骤。通过在真实数据和合成数据上进行数值实验，我们得出鼓舞人心的结果。我们的方法在两个点云描述物体的不同部分（甚至可能没有重叠的情况）时特别有用，前提是该物体的表面可以用一组多项式方程来很好地近似。第一步骤 —— 逼近 —— 是独立感兴趣的，因为它可以用于去噪属于代数变量的数据。我们提供了 Stein 的无偏估计的统计保证来估计去噪的误差。

    Jan, 2024

  • 代数几何中可以计算的内容是什么？

    本文调查了代数几何中的计算问题，着重讨论了 Grobner 基础理论和代数簇的正则性，其中包括几何和代数的介绍，范围、复杂性问题和应用。

    Apr, 1993

  • 相机重新定位的代数与几何

    通过使用 Gröbner 基技术，我们研究了与相机校准问题相关的代数变体，表征了这些校准变体的多分次消失理想。作为应用，我们推导并重新解释了与相机 - 点对偶相关的几何计算机视觉中的著名结果。我们还阐明了在最优校准和三角测量的经典问题之间的一些关系，提出了一个关于校准变体的欧几里德距离度量的猜想式，并讨论了这个猜想与最近解决的多视点猜想的关系。

    Sep, 2023

  • 对数凸多项式 II：高维随机游走和计算拟阵基数的 FPRAS

    本篇论文设计了一种 FPRAS 来计算基于独立集先验的任何线性族的基数，估算处于 $0<q<1$ 区间的任何线性族的随机团模型的分区函数，并证明了任何线性族的基交换图具有至少 1 的扩张，并研究了纯单纯复合物和多项式的密切联系。

    Nov, 2018