公平列子集选择
本文研究理论和实际情况下对列子集选择问题的贪婪算法,并从分布式角度验证其有效性,结合最近在子模最大化中发展的随机可组合核心集思想,提供了改进的近似保证并呈现首个具有可证明近似因子的分布式实现,最后通过实证研究验证了其分布式算法的有效性。
May, 2016
本文定义了一般化的列子集选择问题,该问题涉及从源矩阵 A 中选择少量列,这些列最能逼近目标矩阵 B 的跨度,提出了一种快速贪心算法来解决这个问题,并与可以使用所提出的算法有效解决的不同问题建立联系。
Dec, 2013
提出了一种基于随机列抽样的多项式时间算法,用于选择具有良好谱特性的矩阵子集,具有较高的计算效率和实用价值,并结合 Grothendieck 因子分解构造了一种新的近似算法,以计算矩阵的(无穷大,1)范数。
Jun, 2008
在这篇论文中,我们研究了从大数据集中选择一个小的代表性变量子集的问题,并且证明了计算机科学文献中的维数约简问题(Column Subset Selection)和统计学文献中的寻找最大信息变量集的问题是等价的,同时也可以在一定的半参数模型中视为最大似然估计。利用这些连接,我们展示了如何在仅使用原始数据集的汇总统计信息的情况下有效地进行维数约简(Column Subset Selection),如何在出现缺失和 / 或被审查数据的情况下进行维数约简(Column Subset Selection),以及如何在假设检验框架下选择维数约简(Column Subset Selection)的子集大小。
Jul, 2023
本文通过一个新的两阶段算法,随机选择行矩阵中相应基于前 K 大的奇异空间的概率分布,又应用确定性列选择程序,以 Frobenius 范数和谱范数为衡量指标,分别得到 A 和其最佳秩 K 近似之间的较优边界
Dec, 2008
本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题,并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。
Oct, 2020
研究了不同 ially private top-k 选择问题,提出了基于指数机制和差分隐私组合性质的解决方案,并证明了在高精度区域内,需要 n >= k ln(d)的数据集大小进行高在准的选择。此外,我们还证明了在高精度区域内,选择 k 个最大列所需的数据比估算那些 k 列的值所需的数据量更大。
Feb, 2017
本文提出了利用数据矩阵的谱属性来获得改进的逼近保证,超越了标准的最坏情况分析,研究结果显示:逼近因子作为 k 的函数可能会呈现多个波峰和波谷,这被称为多峰曲线。
Feb, 2020
本文研究了一种矩阵的子集选择问题,其中关注了 Frobenius 范数和谱矩阵范数,并提出了多种新的逼近算法,并证明了在常数因子范围内逼近度是最优的,并且阐述了在一个无向图中找到低拉伸生成树的组合问题与矩阵子集选择问题之间的对应关系及其各种影响。
Dec, 2011
在算法数据分析中,通过随机投影到 “公平” 子空间来减少数据中的偏差,我们将这种方法应用于最密子图问题,理论上和实验上都可以恢复一个几乎最优、公平、稠密的子图,并通过匹配逼近上界展示该问题的 NP - 难度特性。
May, 2019