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

Jun, 2023

Spectral gap-based deterministic tensor completion

Kameron Decker Harris, Oscar López, Angus Read, Yizhe Zhu

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

Abstract

tensor completion is a core machine learning algorithm used in recommender systems and other domains with missing data. While the matrix case is well-understood, theoretical results for tensor problems are limite

tensor completion machine learning recommender systems poisson loss atomic norm minimization

发现论文，激发创造

张量补全的谱算法

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

Dec, 2016

通过核范数最小化进行张量完成

本文探讨了在张量补全中使用矩阵补全技术的不足之处，并证明了直接最小化张量核范数的凸优化方法对于提高样本需求是有益的。我们通过开发一系列代数和概率技术来建立结果，例如张量核范数的次微分的表征以及张量鞅的浓度不等式，这可能对其他张量相关问题具有独立的兴趣和有用性。

May, 2014

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

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

Feb, 2017

非相干张量范数及其在高阶张量补全中的应用

本文研究了高阶张量完成的核范数最小化算法中的样本数量要求，并通过引入一类张量范数，通过利用张量的不相干性，证明了一个阶数为 k，秩为 r，尺寸为 d x ... x d 的张量可以通过适当的不相干核范数最小化算法从仅采样 O（（r ^（k-1）/ 2} d ^ {3/2} + r ^ {k-1} d）（log（d））^ 2）个条目中完美恢复。研究结果不仅指出了当前核范数最小化算法的潜在改进空间，而且还强调了在处理高阶张量时明确考虑不相干性的重要性。

Jun, 2016

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

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

Nov, 2017

来自一般确定性采样模式的矩阵补全

该论文针对低秩矩阵完成算法的理论保证存在严格且近似的情况，可以应用于任何确定性采样计划。通过引入一个图形来解决观察条目的性能问题，论文从理论和实验角度论证了算法的成功性。

Jun, 2023

通用矩阵补全

提出通过使用具有大切比雪夫谱差的二分图边集进行矩阵完成的广泛采样方案，可以精确地恢复所有满足一定不相干性条件的低秩矩阵，而只需 O（nr^2）个随机样本条目。同时改进了已有的矩阵完成算法和核范数方法的分析，与之相比，其样本复杂度为 O（nrlogn）

Feb, 2014

通过整数优化的张量补全

该研究论文中介绍了一种解决张量完备问题的新算法，通过采用基于凸优化问题和基于规范的张量范数的约束来解决计算能力与信息论采样复杂性之间的矛盾，实现了收敛性和信息论速率。

Feb, 2024

低秩矩阵完成的确定性理论

使用图极限理论规定的某一必要且充分条件，对于一系列矩阵补全问题，只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解，该理论是完全确定性的，没有随机性假设，同时列出了一些未解决的问题。

Oct, 2019

通过谱方法改进的排名聚合的理论保证

给定多个项目之间的成对比较，如何对它们进行排名，以使得排名与观察结果相匹配？本研究关注基于 Erdos-Renyi 异常值（ERO）模型的排名问题，在该问题中，每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法，我们提供了每个项目从观察数据中恢复出其潜在分数的性能，并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术，我们提供了更精确的最大特征向量的 l∞范数扰动界限，并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果，并通过数值实验验证了这些理论发现。

Sep, 2023