矩阵补全问题中交替最小化算法的注记
使用一种基于交替最小化的新算法,在标准不连贯性假设下,可从一个未知的低秩矩阵中恢复随机子样本的条目,并减少至少一次方之秩和相似矩阵的条件数的交替最小化方法的样本大小要求。
Dec, 2013
我们开发并分析了一种基于梯度下降(GD)的解决方案,称为交替 GD 和最小化(AltGDmin),以在联邦环境中高效解决低秩矩阵完成(LRMC)问题。我们的理论保证(迭代和样本复杂度界限)表明 AltGDmin 是联邦环境中最高效的解决方案之一,速度最快,并且在所有迭代解 LRMC 的方法中具有第二最佳的样本复杂度。此外,我们还证明了两个重要的推论:(a)我们为 AltGDmin 解决有噪声的 LRMC 问题提供了保证。(b)我们展示了如何利用引理改进 AltMin 的样本复杂度保证,AltMin 是最快的集中式解决方案。
May, 2024
使用图极限理论规定的某一必要且充分条件,对于一系列矩阵补全问题,只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解,该理论是完全确定性的,没有随机性假设,同时列出了一些未解决的问题。
Oct, 2019
本文通过最小化矩阵的核范数,结合已知信息来重建未知的低秩矩阵,并证明了在满足特定的 “不连贯条件” 的情况下,所需的样本量等于参数数量的二次对数因子。这一结论是基于量子信息理论的最新工作,相较于之前的结果,提供了更好的界限。
Oct, 2009
本研究提供了一种有效和稳健的交替最小化框架来解决线性代数和机器学习中的一些问题,关注于都市中加权矩阵的低秩矩阵近似问题,并将运行时间从之前的 n^2k^2 降至 n^2k。
Jun, 2023
本论文研究了基于用户年龄或电影类型等内容信息,预测新用户或新电影评分的电影推荐系统,提出了使用低秩矩阵加特征向量生成评分矩阵的方法,并探讨了使用基于排名的测量值进行低秩矩阵恢复的问题和方法,并在具体三个问题上进行了应用和实验验证。
Jun, 2013
基于最小二乘估计的迭代算法可以用于重建低秩矩阵,并且针对线性结构的矩阵和正半定矩阵等具有先验知识的矩阵,有更好的性能,称为交替最小二乘 (ALS) 算法,并通过模拟实验和 Cramér-Rao 下界进行了比较。
Jun, 2012
本研究提出了一个新的模型以及应用交替最小化算法和两种自适应秩调整策略同时对低秩张量进行低秩矩阵分解,结果表明,该算法可以在比其他方法更少的数据采样下恢复各种合成低秩张量,而且实际数据的测试结果也有类似优势。
Dec, 2013
本文介绍了第一种算法,可在多项式时间和样本复杂度内完成矩阵补全,其复杂度与矩阵的秩成正比,与矩阵的维度成线性关系,与矩阵的条件数成对数关系,并基于交替最小化扩展算法,对标准假设下受噪声影响的情况也有理论保证。
Jul, 2014