该论文提出了一种矩阵完成问题的快速迭代算法,该算法观测到 O (nr^5log^3 n) 的条目,具有确定的样本复杂度,可以解决低秩矩阵恢复的问题。
Nov, 2014
我们提供了一个解决低秩矩阵完成问题的新框架,通过聚合涉及观测的回归问题的解来将矩阵 M 完成,并改进了之前已知的算法的样本复杂度和运行时间。
Aug, 2023
本文通过最小化矩阵的核范数,结合已知信息来重建未知的低秩矩阵,并证明了在满足特定的 “不连贯条件” 的情况下,所需的样本量等于参数数量的二次对数因子。这一结论是基于量子信息理论的最新工作,相较于之前的结果,提供了更好的界限。
Oct, 2009
使用图极限理论规定的某一必要且充分条件,对于一系列矩阵补全问题,只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解,该理论是完全确定性的,没有随机性假设,同时列出了一些未解决的问题。
Oct, 2019
使用一种基于交替最小化的新算法,在标准不连贯性假设下,可从一个未知的低秩矩阵中恢复随机子样本的条目,并减少至少一次方之秩和相似矩阵的条件数的交替最小化方法的样本大小要求。
Dec, 2013
研究了从部分元素中重建低秩矩阵的问题,分析了两种交替最小化算法的变体,证明了当相关矩阵具有秩 $r=1$、有界正元素且图的度和直径在矩阵规模的对数范围内时,两种算法都可以在多项式时间内从任意初始状态开始近似重建矩阵,并提供了模拟结果表明基于信息传递更新的第二个算法表现更好。
Feb, 2016
本文证明了矩阵完成问题即使假设未知矩阵的秩为 4 并且允许输出任意常数秩的矩阵,以及假设未知矩阵不相干并展示 90% 的条目,在 4 着色问题的推测难度性的基础上,矩阵完成问题仍然是计算上难解的;而在标准假设 P≠NP 下,对于正半定矩阵完成问题,我们也展示了类似的难度结果。
Feb, 2014
该研究提出了一种新的低秩矩阵恢复方法,采用非平滑惩罚形式,在某些具体情况下能够克服传统平滑方法的病态问题,同时具有自适应性和鲁棒性。数值实验说明了该方法在解决相位恢复、盲卷积、矩阵补全和稳健 PCA 等计算任务中的优势。
Apr, 2019
本文综述了矩阵完成问题及其与代数几何、组合数学和图论的紧密关系,提出可令任意秩矩阵从一组矩阵项中可辨识的首个必要且充分的组合条件,为矩阵完成问题提出了理论约束和新算法,着重阐述代数 - 组合方法可以超越现有最先进的矩阵完成方法。
Jun, 2012
本文研究低秩矩阵完成问题,提出了一种用于确定有限可完成性的确定性采样条件,展示了在随机采样下,以 O(max(r,log d))的采样数完成矩阵的特定条件可以高概率满足,并探讨了该发现对 LRMC 的意义与应用。
Mar, 2015