广义列子集选择的快速贪心算法
本文研究理论和实际情况下对列子集选择问题的贪婪算法,并从分布式角度验证其有效性,结合最近在子模最大化中发展的随机可组合核心集思想,提供了改进的近似保证并呈现首个具有可证明近似因子的分布式实现,最后通过实证研究验证了其分布式算法的有效性。
May, 2016
提出了一种基于随机列抽样的多项式时间算法,用于选择具有良好谱特性的矩阵子集,具有较高的计算效率和实用价值,并结合 Grothendieck 因子分解构造了一种新的近似算法,以计算矩阵的(无穷大,1)范数。
Jun, 2008
本文通过一个新的两阶段算法,随机选择行矩阵中相应基于前 K 大的奇异空间的概率分布,又应用确定性列选择程序,以 Frobenius 范数和谱范数为衡量指标,分别得到 A 和其最佳秩 K 近似之间的较优边界
Dec, 2008
本文研究了一种矩阵的子集选择问题,其中关注了 Frobenius 范数和谱矩阵范数,并提出了多种新的逼近算法,并证明了在常数因子范围内逼近度是最优的,并且阐述了在一个无向图中找到低拉伸生成树的组合问题与矩阵子集选择问题之间的对应关系及其各种影响。
Dec, 2011
本研究通过分析子模函数的最大化和谱分析的见解,引入了子模性比率作为一种关键性质,研究了从大量随机变量中选择 k 个变量的问题,以实现对另一个感兴趣的变量的最佳线性预测,取得了这个问题方面最强的现有近似保证,并运用了该技术进行了实验和分析。
Feb, 2011
在这篇论文中,我们研究了从大数据集中选择一个小的代表性变量子集的问题,并且证明了计算机科学文献中的维数约简问题(Column Subset Selection)和统计学文献中的寻找最大信息变量集的问题是等价的,同时也可以在一定的半参数模型中视为最大似然估计。利用这些连接,我们展示了如何在仅使用原始数据集的汇总统计信息的情况下有效地进行维数约简(Column Subset Selection),如何在出现缺失和 / 或被审查数据的情况下进行维数约简(Column Subset Selection),以及如何在假设检验框架下选择维数约简(Column Subset Selection)的子集大小。
Jul, 2023
利用基于强化学习的多列选择策略,通过选择最有前途的列以提高目标值和加快收敛速度,比较传统单列和多列选择策略,在切割库存问题和图着色问题中取得了显著的收敛速度和迭代次数的减少。
Dec, 2023