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

Jan, 2015

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

Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra

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

Abstract

In the noisy tensor completion problem we observe $m$ entries (whose location is chosen uniformly at random) from an unknown $n_1 \times n_2 \times n_3$ tensor $T$. We assume that $T$ is entry-wise close to being rank $r$. Our goal is to fill in its missing entries using as few observa

noisy tensor completion sum-of-squares rademacher complexity overcomplete algorithm

发现论文，激发创造

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

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

Feb, 2017

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

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

Nov, 2017

张量补全的谱算法

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

Dec, 2016

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

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

Apr, 2015

低秩张量环噪声张量补全

本文提出了一种新的噪声张量补全模型，结合了张量环核范数和最小二乘估计器来正则化原始张量和观测条目，通过优化算法以实现高效且精确地预测缺失条目。

Mar, 2022

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

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

Apr, 2013

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

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

Oct, 2016

Cross: 高效低秩张量补全

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

Nov, 2016

从含噪数据中恢复低秩张量的非凸方法

我们提出了一个两阶段的非凸算法，用于从高度不完整和随机损坏的观测值中重建低秩张量，并在几乎线性时间内恢复所有单个张量因子，同时享受接近最优的统计保证，我们还讨论了如何扩展我们的方法以适应非对称张量。

Nov, 2019

核范数惩罚和噪音下低秩矩阵完备的最优速率

本文研究迹回归模型，提出一种新的核范数惩罚估计器用于矩阵补全问题，并证明了其比以前的方法具有更快的收敛速度的预言不等式。最后，我们表明我们的程序提供了 $A_0$ 数据的秩的准确恢复。

Nov, 2010