Nov, 2009

大多数张量问题是 NP 难问题

PDF
TL;DR证明了在数值线性代数中，许多高效可计算问题的多线性（张量）形式都是 NP 难的。其中包括决定一个双线性方程组的可行性，确定一个三阶张量是否具有给定的特征值，奇异值或谱范数；逼近特征值，特征向量，奇异向量或谱范数；确定三阶张量的秩或最佳秩 - 1 逼近等问题，以及证明了将这些问题限制在对称张量中并不能缓解它们的 NP 难度。通过证明 NP 难性，进一步指出了线性 / 凸问题计算可行性和非线性 / 非凸问题计算可行性之间的边界。
发现论文，激发创造
  • 张量秩有多难？

    探讨张量秩的计算复杂性，对任意整环上的张量证明了秩问题与该整环上的多项式方程组问题的多项式时间等价性，同时得出了对称秩和矩阵补全问题的类似结论。

    Nov, 2016

  • 张量及其 Tucker 核 ：不变关系

    本文研究了张量的 Tucker 核，证明它具有原张量的多项式秩、模、边框秩和 Z - 特征值，这导致了很大的计算优势。

    Jan, 2016

  • 高阶张量的核范数

    本文探讨了高阶张量的核范数的数学和计算特性，发现核范数与张量秩一样取决于基域的选择，并且证明了对于对称张量，它的对称核范数总是等于其核范数。此外，本文还证明了计算张量核范数在多个方面上是 NP 难问题。

    Oct, 2014

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

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

    Dec, 2022

  • 通过核范数最小化保证线性矩阵方程的最小秩解

    本文研究了在满足给定的线性等式约束的前提下寻找一个满足最小秩的矩阵的问题，证明在线性变换满足一定的保型性条件下，可以通过解决一个凸优化问题来恢复最小秩解，即在给定仿射空间上，通过最小化核范数来建立几个随机方程整体满足保型性条件，进而将基数最小化的概念推广到秩最小化上。

    Jun, 2007

  • 张量秩与最佳低秩逼近问题的病态性

    本文讨论了针对高于三阶的张量的最优低秩逼近定理。我们提出了使用弱解来克服低秩逼近问题的不适定性，并从代数几何的角度将我们的工作与张量的现有研究联系起来。

    Jul, 2006

  • 张量的特征值数量

    通过研究多线性数值代数中最近研究的张量的本征向量，我们确定了一般张量的本征向量和本征值的数量，并且证明了对称张量的归一化本征值的数量总是有限的。我们还研究了特征多项式及其系数与鉴别式和结果的关系。

    Apr, 2010

  • 关于偏导数的复杂度

    本文考虑基于偏导数的一种复杂度度量，研究了计算偏导数空间维度的复杂性问题。作者使用轨迹方法给出了偏导数维度的合理下界，并留下了一个近似算法的开放问题。

    Jul, 2016

  • 平面计数问题的复杂性

    在平面图情况下，我们证明了与各种满足性、图形和组合问题相关的计数问题的 #P 难度。另外，当局限于计划实例时，我们证明了具有不明确解决方案性的满足性问题的 NP 完全性和与唯一满足性问题相关的随机多项式可简化的 DP 完全性。假设 P≠NP，则以上结果的一个推论是：不存在 ε- 逼近算法，用于在整数上计划线性不等式约束系统的最大化或最小化线性目标函数问题。

    Sep, 1998

  • 非负张量的非负逼近

    研究对一个非负张量进行分解为非负向量的最小外积和对应的简化的朴素贝叶斯概率模型，并证明该问题的逼近问题，无论采用哪种规范，甚至是布雷格曼分歧，都将始终具有最优解。

    Mar, 2009