Mar, 2015

低秩矩阵完成的确定性采样模式表征

PDF
TL;DR本文研究低秩矩阵完成问题，提出了一种用于确定有限可完成性的确定性采样条件，展示了在随机采样下，以 O（max（r，log d））的采样数完成矩阵的特定条件可以高概率满足，并探讨了该发现对 LRMC 的意义与应用。
low-rank matrix completiondeterministic conditionsfinite completabilitysampling schemescomputational complexity
发现论文，激发创造
  • 来自一般确定性采样模式的矩阵补全

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

    Jun, 2023

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

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

    Oct, 2019

  • 矩阵补全的计算限制

    本文证明了矩阵完成问题即使假设未知矩阵的秩为 4 并且允许输出任意常数秩的矩阵，以及假设未知矩阵不相干并展示 90% 的条目，在 4 着色问题的推测难度性的基础上，矩阵完成问题仍然是计算上难解的；而在标准假设 P≠NP 下，对于正半定矩阵完成问题，我们也展示了类似的难度结果。

    Feb, 2014

  • 低秩矩阵补全：当代综述

    本文为低秩矩阵补全问题提供了最新的调查，对最新的 LRMC 技术进行了分类和详细说明，讨论了 LRMC 技术使用时需要考虑的问题，并介绍了基于卷积神经网络的 LRMC 算法，最后介绍了最新 LRMC 技术的恢复性能和计算复杂性。希望本文对初学者和从业者提供了有用的指导。

    Jul, 2019

  • 关于矩阵完成和逼近中自适应能力的探讨

    本文介绍了一种自适应采样算法，可以高效地完成低秩近似和矩阵填充任务，并且消除了之前文献中存在的某些限制性假设，具有更好的采样复杂度。

    Jul, 2014

  • 一种组合代数方法用于低秩矩阵补全的可识别性

    本文综述了矩阵完成问题及其与代数几何、组合数学和图论的紧密关系，提出可令任意秩矩阵从一组矩阵项中可辨识的首个必要且充分的组合条件，为矩阵完成问题提出了理论约束和新算法，着重阐述代数 - 组合方法可以超越现有最先进的矩阵完成方法。

    Jun, 2012

  • 可证明地补全任意低秩矩阵

    本文提出了一种特定偏向分布的采样方式，利用该采样方式可以从少量采样的数据中精确恢复任何秩为 r 的 nxn 的矩阵（无需满足之前已有的结构限制要求），而且在没有先验信息下本文建立了三种使用该采样方式的方法，其中还包括分析了针对非均匀采样情形中，加权核范数 / 迹范数惩罚的优点。

    Jun, 2013

  • 有限样本下精确快速矩阵补全

    该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O (nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。

    Nov, 2014

  • 刚体理论下的低秩矩阵完备性唯一性

    矩阵完成问题和距离几何问题之间具有类似性质，利用刚性理论的工具，可以设计出用于测试矩阵局部或全局唯一完成性的高效随机算法。

    Feb, 2009

  • 几乎验证时间内的矩阵完成

    我们提供了一个解决低秩矩阵完成问题的新框架，通过聚合涉及观测的回归问题的解来将矩阵 M 完成，并改进了之前已知的算法的样本复杂度和运行时间。

    Aug, 2023