凸松弛的威力:近似最优矩阵补全
本研究论文介绍新兴的矩阵填充技术及其应用,其中最简单的情况是从一个数据样本中恢复一个数据矩阵。本文提出通过核范数极小化技术,按数据约束条件恢复矩阵,可在一定程度下证明矩阵填充的准确性,数值结果表明,核范数极小化技术可以在很少的观测样本中准确填充低秩矩阵的许多缺失条目。
Mar, 2009
本文通过最小化矩阵的核范数,结合已知信息来重建未知的低秩矩阵,并证明了在满足特定的 “不连贯条件” 的情况下,所需的样本量等于参数数量的二次对数因子。这一结论是基于量子信息理论的最新工作,相较于之前的结果,提供了更好的界限。
Oct, 2009
本文介绍了一种新的算法,用于近似矩阵和满足一组凸约束条件的所有矩阵中具有最小核范数的矩阵。该算法可在低阶矩阵完成问题上使用,具有快速计算的特点,通过少量存储空间实现低计算代价。
Oct, 2008
本文研究了针对大规模低秩矩阵的部分和带噪声数据中的矩阵补全问题,采用凸松弛和 Burer-Monteiro 方法,成功地将凸松弛的实践与非凸方法的统计保证相结合,取得了近乎最优的估计误差。
Feb, 2019
通过将低秩矩阵补全问题重新表述为在投影矩阵的非凸集上的凸问题,并实施一个可证明最优的分离分支限界方案,推导出一类新的收敛松弛方法。数值实验表明,相比现有的收敛松弛方法,我们的新型收敛松弛方法将最优性差距降低了两个数量级。此外,我们展示了我们的分离分支限界方案的性能,并展示了它在解决矩阵完成问题方面的优异表现。
May, 2023
提出通过使用具有大切比雪夫谱差的二分图边集进行矩阵完成的广泛采样方案,可以精确地恢复所有满足一定不相干性条件的低秩矩阵,而只需 O(nr^2)个随机样本条目。同时改进了已有的矩阵完成算法和核范数方法的分析,与之相比,其样本复杂度为 O(nrlogn)
Feb, 2014
使用图极限理论规定的某一必要且充分条件,对于一系列矩阵补全问题,只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解,该理论是完全确定性的,没有随机性假设,同时列出了一些未解决的问题。
Oct, 2019
本文解决了一种矩阵完成问题,特别是当某些列完全且任意被污染,通过一个修剪和凸程序的组合,最小化核范数和 l (1,2) 范数,我们的理论结果表明,即使观察到的条目比例很小,也可以完成底层矩阵,即使被污染的列的数量增加,还可以进行矩阵完成。
Feb, 2011