列子集选择是 NP 完备问题
本文通过一个新的两阶段算法,随机选择行矩阵中相应基于前 K 大的奇异空间的概率分布,又应用确定性列选择程序,以 Frobenius 范数和谱范数为衡量指标,分别得到 A 和其最佳秩 K 近似之间的较优边界
Dec, 2008
本文提出了利用数据矩阵的谱属性来获得改进的逼近保证,超越了标准的最坏情况分析,研究结果显示:逼近因子作为 k 的函数可能会呈现多个波峰和波谷,这被称为多峰曲线。
Feb, 2020
在这篇论文中,我们研究了从大数据集中选择一个小的代表性变量子集的问题,并且证明了计算机科学文献中的维数约简问题(Column Subset Selection)和统计学文献中的寻找最大信息变量集的问题是等价的,同时也可以在一定的半参数模型中视为最大似然估计。利用这些连接,我们展示了如何在仅使用原始数据集的汇总统计信息的情况下有效地进行维数约简(Column Subset Selection),如何在出现缺失和 / 或被审查数据的情况下进行维数约简(Column Subset Selection),以及如何在假设检验框架下选择维数约简(Column Subset Selection)的子集大小。
Jul, 2023
提出了一种基于随机列抽样的多项式时间算法,用于选择具有良好谱特性的矩阵子集,具有较高的计算效率和实用价值,并结合 Grothendieck 因子分解构造了一种新的近似算法,以计算矩阵的(无穷大,1)范数。
Jun, 2008
本文研究了一种矩阵的子集选择问题,其中关注了 Frobenius 范数和谱矩阵范数,并提出了多种新的逼近算法,并证明了在常数因子范围内逼近度是最优的,并且阐述了在一个无向图中找到低拉伸生成树的组合问题与矩阵子集选择问题之间的对应关系及其各种影响。
Dec, 2011
本文定义了一般化的列子集选择问题,该问题涉及从源矩阵 A 中选择少量列,这些列最能逼近目标矩阵 B 的跨度,提出了一种快速贪心算法来解决这个问题,并与可以使用所提出的算法有效解决的不同问题建立联系。
Dec, 2013
我们介绍了一种用于矩阵恢复问题的两步方法,结合了列子集选择和低秩矩阵补全问题的理论基础。该方法通过两个凸优化任务来求解,我们提出了两个算法来实现 Columns Selected Matrix Completion(CSMC)方法,分别针对不同规模的问题。我们对该方法进行了正式的分析,在分析中我们给出了必要的假设和找到正确解的概率。在论文的第二部分,我们展示了实验结果。通过在合成数据上进行实验,我们研究了矩阵大小、秩和缺失元素比例对解的质量和计算时间的影响。该方法还应用于两个实际问题:推荐系统中的电影评分预测和图像修复。我们的彻底分析显示 CSMC 能够提供与基于凸优化的矩阵补全算法相当的解的质量,但在运行时间上具有显著的节省。
Mar, 2024
证明对于任意实值矩阵 X,在正整数 r≥k 的情况下,存在 X 的 r 个列的子集,将 X 投影到其中一个列的线性组合中,得出的结果将是 Frobenius 范数下的 X 的最佳秩 - k 逼近的一个近似值等于 sqrt ((r + 1)/(r-k +1))。并提出一个确定性算法可在 O (r n m^ω log m) 时间内找到这样的列的子集,其中 ω 是矩阵乘法的指数。同样,我们提供了一种更快的随机算法,可在 O (r n m^2) 时间内进行运算。
Apr, 2011
本文针对正半定矩阵逼近的问题进行研究,提出了一个原型模型并建立了相应的错误边界,该模型具有更高的可扩展性和有效性。同时,本文提出了新的理论分析、高效算法和更为精确的扩展方法,并通过降低误差边界、改进现有的列选择算法,开发一种简单的选择算法,以及提出了一种谱移动模型来提高逼近的精度。
Jun, 2014