高阶张量的核范数
本文研究了 $3$ 维张量的核范数及其矩阵展开的核范数之间的关系,并提出了相应的上下界和计算标准,进一步推广到 $N$ 维张量,并在 $N=3$ 的情况下获得了最优解。
Dec, 2014
针对具有一定次数的 n 维张量,在一定的次高斯假设下,我们通过覆盖数量的论证,证明其谱范数的上界与张量各维度大小之和及其对数成正比,从而得出该张量的核范数具有较低样本复杂度,该结论相比于其他基于展开的张量低秩凸松弛方法而言具有更小的复杂度。
Jul, 2014
本文探讨了在张量补全中使用矩阵补全技术的不足之处,并证明了直接最小化张量核范数的凸优化方法对于提高样本需求是有益的。我们通过开发一系列代数和概率技术来建立结果,例如张量核范数的次微分的表征以及张量鞅的浓度不等式,这可能对其他张量相关问题具有独立的兴趣和有用性。
May, 2014
本文研究了高阶张量完成的核范数最小化算法中的样本数量要求,并通过引入一类张量范数,通过利用张量的不相干性,证明了一个阶数为 k,秩为 r,尺寸为 d x ... x d 的张量可以通过适当的不相干核范数最小化算法从仅采样 O((r ^(k-1)/ 2} d ^ {3/2} + r ^ {k-1} d)(log(d))^ 2)个条目中完美恢复。研究结果不仅指出了当前核范数最小化算法的潜在改进空间,而且还强调了在处理高阶张量时明确考虑不相干性的重要性。
Jun, 2016
本文研究了张量核范数在 Guassian measurements 下的低秩张量恢复问题,证明了 TNN 是一种特殊的原子范数,并提出了 TNN 最小化问题的解决方案。通过实验验证了理论结果。
Jun, 2018
使用 sum-of-squares 层次结构的思想,我们提供了第一个几乎多项式时间复杂度的算法,可以在分解随机 3 阶张量时,将秩提高到 $n^{3/2} / extrm {polylog} n$。我们还提出了一种检验低秩张量的 injective norm 的多项式时间复杂度算法,并证明了这个算法的正确性。
Apr, 2015
本篇论文探讨了基于 Schmidt 分解定理定义的一族向量和算子范数,并使用这些范数解决了量子信息理论中的两个基本问题:k - 正线性映射和纠缠证人的分类问题,以及非正偏转限制纠缠态的存在问题。
Sep, 2009
研究线性算子 2->q 范数的计算复杂性,该范数定义为 ||A||_{2->q}=sup_v||Av||_q/||v||_2,以及这个问题与量子信息理论和 Khot 的唯一游戏猜想 (UGC) 的问题之间的联系。
May, 2012
本文针对张量鲁棒主成分分析问题,提出了基于张量张量积的模型,并在此基础上推出了张量谱范数,张量核范数和张量平均秩,集中研究了它们的特性和联系,并在此基础上解决张量鲁棒主成分分析问题,提供了准确恢复的理论保证,相关实验在图像恢复和背景建模领域表现良好。
Apr, 2018
证明了在数值线性代数中,许多高效可计算问题的多线性(张量)形式都是 NP 难的。其中包括决定一个双线性方程组的可行性,确定一个三阶张量是否具有给定的特征值,奇异值或谱范数;逼近特征值,特征向量,奇异向量或谱范数;确定三阶张量的秩或最佳秩 - 1 逼近等问题,以及证明了将这些问题限制在对称张量中并不能缓解它们的 NP 难度。通过证明 NP 难性,进一步指出了线性 / 凸问题计算可行性和非线性 / 非凸问题计算可行性之间的边界。
Nov, 2009