该论文探讨了如何从其少量项目中恢复未知矩阵的问题,提出使用 “核规范” 法将矩阵恢复降低至在信息论极限附近的数列,以有效提高了恢复矩阵的准确性。
Mar, 2009
使用图极限理论规定的某一必要且充分条件,对于一系列矩阵补全问题,只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解,该理论是完全确定性的,没有随机性假设,同时列出了一些未解决的问题。
Oct, 2019
提出通过使用具有大切比雪夫谱差的二分图边集进行矩阵完成的广泛采样方案,可以精确地恢复所有满足一定不相干性条件的低秩矩阵,而只需 O(nr^2)个随机样本条目。同时改进了已有的矩阵完成算法和核范数方法的分析,与之相比,其样本复杂度为 O(nrlogn)
Feb, 2014
本研究论文介绍新兴的矩阵填充技术及其应用,其中最简单的情况是从一个数据样本中恢复一个数据矩阵。本文提出通过核范数极小化技术,按数据约束条件恢复矩阵,可在一定程度下证明矩阵填充的准确性,数值结果表明,核范数极小化技术可以在很少的观测样本中准确填充低秩矩阵的许多缺失条目。
通过解决凸优化问题,可以从数据矩阵的不完全采样中完美地恢复低秩矩阵,并且这个结果被扩展到了压缩感知。
May, 2008
研究低秩矩阵和张量完成,提出了采用自适应抽样方案的新算法,它们具有强大的性能保证,并能够恢复具有噪声干扰的低秩矩阵。
Apr, 2013
低秩矩阵补全问题关注使用稀疏观测的一组观测条目来估计矩阵中未观测的条目。我们考虑非均匀设置,其中观测条目根据高度变化的概率进行采样,可能具有不同的渐近尺度。我们证明了在结构化采样概率下,使用较小的子矩阵而不是整个矩阵上运行估计算法通常更好,有时是最优的。特别地,在某些条件下,我们证明了适用于每个条目的错误上界,这些错误上界与最小化下界相匹配。我们提供了数值实验证实了我们的理论发现。
Feb, 2024
本文研究如何从观测到的随机稀疏矩阵子集中重建一个秩较低的随机矩阵,提供相应的算法并给出一些误差保证以及时间复杂度估计,并得到一些稀疏随机矩阵谱的推广结果。
Jan, 2009
本文证明了矩阵完成问题即使假设未知矩阵的秩为 4 并且允许输出任意常数秩的矩阵,以及假设未知矩阵不相干并展示 90% 的条目,在 4 着色问题的推测难度性的基础上,矩阵完成问题仍然是计算上难解的;而在标准假设 P≠NP 下,对于正半定矩阵完成问题,我们也展示了类似的难度结果。
研究了张量恢复中的样本量要求,提出梯度下降算法结合谱方法来重建低秩高阶张量,事实证明我们的方法在保证高概率的情况下只需要 O (r^7/2*d^3/2*log^7/2 (d)+r^7*d*log^6 (d)) 个样本,且可以很好地处理低秩多线性张量,相对于其他方法具有高效易用性的优点。
Feb, 2017