本文研究了带权低秩逼近算法的计算复杂度,并证明了即使在寻求秩为一的逼近解时,找到近似解也是 NP 难的,该证明基于最大边双团问题的约化并适用于严格正权重和二进制权重。
Dec, 2010
本文介绍了低秩逼近技术,并给出了众多相关技术的广泛参考资料。在此基础上,简要评述了基于奇异值分解、QR 分解、随机算法以及交叉 / 骨架逼近等各种低秩逼近技术的应用和优缺点。
Jun, 2016
本文介绍了一种基于学习的算法来解决低秩分解问题,并且通过学习用稀疏矩阵来代替随机矩阵可以减小近似误差。同时,给出了针对稀疏矩阵学习问题的泛化界及近似算法。
Oct, 2019
提出了一种新的框架 SLOMA,将社交网络信息引入到 Local Low-Rank Matrix Approximation 中,结合社交推荐和本地低秩假设可以更好地解决推荐系统中的问题。
Apr, 2017
介绍了一种在保证模型精度的情况下,同时降低深度学习中推理和训练成本,并通过基于神经网络条件数的模型稳健性表明低秩矩阵分解(low-rank matrix factorizations)容易导致模型鲁棒性的问题,提出了一种基于鲁棒低秩矩阵训练的算法,通过施加近似正交约束,保证了低秩表示与近似完整的模型之间精度。通过实验证明降低深度学习模型中推理和训练成本的同时,提高了模型的鲁棒性。
Jun, 2023
本文研究了在正定核框架下的监督学习问题,提出了基于随机矩阵列采样的核矩阵低秩近似方法,此方法可以在 sub-quadratic 的时间复杂度内有效解决核矩阵计算问题,同时保持预测性能不变。
Aug, 2012
本文综述了利用低秩结构在信号处理和机器学习中进行矩阵恢复的现代方法,重点介绍了实践中最常用的算法,这些算法的现有理论保证以及这些技术的代表性实践应用。
Jan, 2016
低秩建模在信号处理和机器学习中扮演着关键的角色,本文综述了利用凸和非凸方法对低秩矩阵估计进行计算上高效可证的方法,其中包括对低维子空间和流形的适当利用及其对计算和存储成本的显著降低。
Feb, 2018
本研究探讨了分布式低秩逼近,其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明,在宽泛的函数 f 类别中,可以高效计算一个低秩映射矩阵 P,以满足通信成本为 d∙(sk/ε)^O (1),且算法成功概率高,并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。
本文提出了一种基于社区检测和流形学习的矩阵完成模型,通过约束矩阵在图上的平滑性来隐含地强制行和列之间的相似性,得到了比标准模型更好的矩阵恢复效果。
Aug, 2014