Dec, 2016

张量补全的谱算法

PDF
TL;DR该研究提出了基于展开的新方法，其中一个应用是特征空间估计。研究者针对张量完成问题，提出了两种方法，一种是采用 SOS 方法，但不适合处理大规模问题；另一种是采用展开或者矩阵分解方法，在解决三阶张量问题时性能和 SOS 方法相当。
tensor completionsum-of-squaresspectral methodssingular space estimationrandom model
发现论文，激发创造
  • 关于精确低秩张量完成的多项式时间方法

    研究了张量恢复中的样本量要求，提出梯度下降算法结合谱方法来重建低秩高阶张量，事实证明我们的方法在保证高概率的情况下只需要 O (r^7/2*d^3/2*log^7/2 (d)+r^7*d*log^6 (d)) 个样本，且可以很好地处理低秩多线性张量，相对于其他方法具有高效易用性的优点。

    Feb, 2017

  • 基于谱间隙的确定性张量补全

    本文介绍了两种基于 Poisson loss 和 atomic norm minimization 的张量补全方法，提出了更紧密的界限，描绘了其对目标张量秩的关系，并探讨了最大准范数、岭惩罚和 Poisson 损失减小算法的实用性。

    Jun, 2023

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

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

    Nov, 2017

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

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

    Feb, 2017

  • 通过平方和层次法实现带噪声张量补全

    该论文提出了一种基于六阶 sum-of-squares 层次结构的多维张量补全算法，其在观察到 $n^{3/2} r$ 个条目时能够在多项式时间内完成补全，并且该算法具有通用性，可以处理维度 $r > n$ 的张量补全问题。

    Jan, 2015

  • 使用平方和算法分解超完备的三阶张量

    使用 sum-of-squares 层次结构的思想，我们提供了第一个几乎多项式时间复杂度的算法，可以在分解随机 3 阶张量时，将秩提高到 $n^{3/2} / extrm {polylog} n$。我们还提出了一种检验低秩张量的 injective norm 的多项式时间复杂度算法，并证明了这个算法的正确性。

    Apr, 2015

  • 基于平方和证明的快速谱算法：张量分解和种植稀疏向量

    研究了两个基于机器学习应用中的问题：在随机线性子空间中恢复种植稀疏向量的问题以及分解随机低秩超完备三阶张量的问题。通过分析和受到二次和方法的启发，提出了新的算法，其可以在更快的时间内实现与二次和方案相似的保证

    Dec, 2015

  • 自适应采样的低秩矩阵和张量补全

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

    Apr, 2013

  • 多项式时间的带有平方和项的张量分解

    本文基于平方和方法给出了用于张量分解的新算法，结果改进了多个问题的运行时间，包括对超完备三元组分解和具有常数相对稀疏度的超完备字典的学习等问题的算法，同时首次在平滑分析模型中给出了超完备四元组分解的稳健性分析。而此分析的关键因素在于在由平方和松弛解导出的矩阵时刻中建立小的谱间隙，为了使此分析成为可能，本文将最大熵约束的谱同构加到平方和松弛约束上。

    Oct, 2016

  • 基于平方和证明的张量主成分分析

    研究了一个针对张量主成分分析问题的统计模型，通过基于四次幂和松弛的舍入算法，证明了随机噪声张量的种植向量可以在高概率下被回收，还证明了四次幂和松弛在一定程度下是不起作用的，研究并利用了额外的问题结构来求解我们的平方和松弛。

    Jul, 2015