Aug, 2023

底秩张量恢复的一阶方法的效率研究：严格互补条件下的张量核范数

PDF
TL;DR使用凸松弛方法，基于张量核范数引入的球形约束最小化来恢复低秩张量，引入张量核范数球的适当严格互补条件下获得重要结果，包括线性收敛速度、低秩解的近似线性运行时间，在非平滑目标函数中类似结果可用于 extragradient 方法，并扩展了先前仅适用于三阶张量的许多基本结果。
发现论文，激发创造
  • 通过核范数最小化进行张量完成

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

    May, 2014

  • 高斯测量下精确低秩张量回收

    本文研究了张量核范数在 Guassian measurements 下的低秩张量恢复问题，证明了 TNN 是一种特殊的原子范数，并提出了 TNN 最小化问题的解决方案。通过实验验证了理论结果。

    Jun, 2018

  • 关于使用低秩投影的投影梯度方法收敛于迹范数球约束下的平滑凸规划及相关问题

    本文介绍了一种使用低秩 SVD 计算的简单启发式算法，使得标准一阶方法可以实现局部收敛，并可用于平滑凸规划的计算，以及带缩放梯度正则化和约束半正定矩阵上的计算。这些计算为机器学习，信号处理和统计学等领域中底秩矩阵恢复问题提供了实质性帮助。

    Feb, 2019

  • 方形交易：张量恢复的下界和改进的松弛

    本文提出一种新的简单的基于凸松弛的方法，并通过模拟实验证明其在低秩张量恢复方面性能更好，这有可能通过同时利用多种结构来降低样本复杂度。

    Jul, 2013

  • 高阶张量恢复与张量 U1 范数

    我们提出了一种新的张量分解和一种新的张量范数，称为张量 $U_1$ 范数，用于解决高阶张量数据的完整性问题，并提出了一个优化算法来解决该问题。该方法在处理具有非光滑变化的张量数据方面表现出良好效果。

    Nov, 2023

  • 一种新的基于张量分解的方法，对不精确秩估计具有鲁棒性

    本文提出了一种新的张量范数，同时利用低秩先验和秩信息，包括一系列张量管秩的代理函数，可在张量数据中更好地利用低秩，通过使用样本技巧计算更小张量的 t-SVD 而不是原始张量来计算提出的双低秩约束的张量范数。随后，优化算法的每个迭代的计算成本从标准方法的 O (n^4) 降低到 O (n^3 log n + kn^3)，其中 k 为真实张量秩的估计值，远小于 n。本方法在合成和现实数据上得到了评估，并表现出优于现有 STOA 张量完成方法的性能和效率。

    May, 2023

  • 高效的结构化矩阵秩最小化

    利用核范数正则化寻找结构化低秩矩阵的问题，我们采用线性映射来编码结构，并提出了一种更有效的方法，与同类方法相比，该方法在迭代次数和计算成本上都有所改善，并在随机系统实现和光谱压缩感知问题中表现出色。

    Sep, 2015

  • 张量补全的新凸松弛方法

    该论文研究了如何通过欧几里得球的凸松弛和乘子法方法解决张量学习中由于痕迹规范化限制而存在的限制，并在合成和真实数据集上对该方法进行了验证，表明其估计误差显著降低，同时保持计算可行性。

    Jul, 2013

  • 使用 t-SVD 进行精确张量补全

    本文利用张量奇异值分解求得张量的秩概念 —— 张量管秩，使用具有优化性质的张量核范数最小化的凸优化问题，完成了从有限采样中完成高维数据恢复的任务，并证明了此方法的有效性。

    Feb, 2015

  • 低秩外梯度方法用于可扩展半定规划优化

    我们研究了涉及具有凸目标函数（平滑或非平滑）和额外的线性或非线性平滑凸约束的几类非常重要的半定优化问题，这些问题在统计学、机器学习、组合优化和其他领域中非常普遍。我们关注高维和合理设置的情况，在这种情况下，问题具有满足低秩互补条件的低秩解。我们提供了几个理论结果，证明在这些情况下，众所周知的 Extragradient 方法，在在接近最优原始 - 对偶解的位置初始化时，使用低秩奇异值分解（SVD）将收敛到约束优化问题的解，并具有标准收敛速度保证，而不需要在最坏情况下需要计算成本高昂的全秩 SVD。我们的方法得到了使用 Max-Cut 实例数据集进行的数值实验的支持。

    Feb, 2024