Feb, 2017

关于精确低秩张量完成的多项式时间方法

PDF
TL;DR研究了张量恢复中的样本量要求，提出梯度下降算法结合谱方法来重建低秩高阶张量，事实证明我们的方法在保证高概率的情况下只需要 O (r^7/2*d^3/2*log^7/2 (d)+r^7*d*log^6 (d)) 个样本，且可以很好地处理低秩多线性张量，相对于其他方法具有高效易用性的优点。
tensor recoverylow-rankmultilineargradient descent algorithmsample size requirement
发现论文，激发创造
  • 自适应采样的低秩矩阵和张量补全

    研究低秩矩阵和张量完成，提出了采用自适应抽样方案的新算法，它们具有强大的性能保证，并能够恢复具有噪声干扰的低秩矩阵。

    Apr, 2013

  • 具有平方和形式的张量精确完成

    本研究使用最优的多项式算法，仅依靠少量随机观察数据完成张量解析，并将通过球上的正交全局极值证明的事实证明到可以在和方法证明系统内进行。

    Feb, 2017

  • 张量补全的谱算法

    该研究提出了基于展开的新方法，其中一个应用是特征空间估计。研究者针对张量完成问题，提出了两种方法，一种是采用 SOS 方法，但不适合处理大规模问题；另一种是采用展开或者矩阵分解方法，在解决三阶张量问题时性能和 SOS 方法相当。

    Dec, 2016

  • 噪声输入下从低秩张量恢复的统计最优和计算高效方法

    本研究提出了一种基于幂迭代和二阶谱初始化的计算低秩张量的方法，该方法能够实现低噪声干扰下的统计和计算效率，并能够达到最优收敛速率。

    Nov, 2017

  • 带有缺失数据的可证明张量分解

    本文研究低秩张量分解在缺失数据的情况下的问题，提出了基于交替最小化法的新方法，表明在一定条件下，我们的方法可以从少量采样的条目中精确地恢复一个低秩张量。

    Jun, 2014

  • Riemannian 优化在低秩矩阵补全中的保证

    研究嵌入低秩矩阵流形的黎曼优化方法在矩阵补全问题上的应用和收敛性，其中采样复杂度能进一步通过重新采样的黎曼梯度下降初始化方法减小，这取决于采样算子的像的非对称限制性同构性质和低秩矩阵流形的曲率。

    Mar, 2016

  • 矩阵完成的简单方法

    本文通过最小化矩阵的核范数，结合已知信息来重建未知的低秩矩阵，并证明了在满足特定的 “不连贯条件” 的情况下，所需的样本量等于参数数量的二次对数因子。这一结论是基于量子信息理论的最新工作，相较于之前的结果，提供了更好的界限。

    Oct, 2009

  • 有限样本下精确快速矩阵补全

    该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O (nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。

    Nov, 2014

  • 低秩张量补全的并行矩阵分解

    本研究提出了一个新的模型以及应用交替最小化算法和两种自适应秩调整策略同时对低秩张量进行低秩矩阵分解，结果表明，该算法可以在比其他方法更少的数据采样下恢复各种合成低秩张量，而且实际数据的测试结果也有类似优势。

    Dec, 2013

  • Cross: 高效低秩张量补全

    本研究提出了一种基于交叉测量方案的低秩张量完备性方法，可从噪声测量中恢复出高阶低秩张量，其样本复杂度匹配样本复杂度下限，并在神经影像学数据中进行了演示。

    Nov, 2016