Feb, 2020

对于纵列子集选择和 Nyström 方法的改进保证和多下降曲线

PDF
TL;DR本文提出了利用数据矩阵的谱属性来获得改进的逼近保证，超越了标准的最坏情况分析，研究结果显示：逼近因子作为 k 的函数可能会呈现多个波峰和波谷，这被称为多峰曲线。
column subset selection problemnyström methodlow-rank approximationsspectral propertiessingular value decay
发现论文，激发创造
  • 列子集选择是 NP 完备问题

    本研究探讨了矩阵 CSSP 问题在数字线性代数中的应用和算法复杂度，并证明了其为 NP 完全问题。

    Jan, 2017

  • 列子集选择问题的改进近似算法

    本文通过一个新的两阶段算法，随机选择行矩阵中相应基于前 K 大的奇异空间的概率分布，又应用确定性列选择程序，以 Frobenius 范数和谱范数为衡量指标，分别得到 A 和其最佳秩 K 近似之间的较优边界

    Dec, 2008

  • 通过列选择进行 SPSD 矩阵近似：理论、算法和扩展

    本文针对正半定矩阵逼近的问题进行研究，提出了一个原型模型并建立了相应的错误边界，该模型具有更高的可扩展性和有效性。同时，本文提出了新的理论分析、高效算法和更为精确的扩展方法，并通过降低误差边界、改进现有的列选择算法，开发一种简单的选择算法，以及提出了一种谱移动模型来提高逼近的精度。

    Jun, 2014

  • 基于统计的列子集选择视角

    在这篇论文中，我们研究了从大数据集中选择一个小的代表性变量子集的问题，并且证明了计算机科学文献中的维数约简问题（Column Subset Selection）和统计学文献中的寻找最大信息变量集的问题是等价的，同时也可以在一定的半参数模型中视为最大似然估计。利用这些连接，我们展示了如何在仅使用原始数据集的汇总统计信息的情况下有效地进行维数约简（Column Subset Selection），如何在出现缺失和 / 或被审查数据的情况下进行维数约简（Column Subset Selection），以及如何在假设检验框架下选择维数约简（Column Subset Selection）的子集大小。

    Jul, 2023

  • 公平列子集选择

    研究公平的列子集选择问题，尤其是在考虑多个数据群体的情况下，采用一种基于确定性杠杆得分采样的方法来提高选择近似解的效果。

    Jun, 2023

  • 重新审视 Nystrom 方法以改进大规模机器学习

    本篇研究论文旨在重新考虑随机算法用于对称半正定矩阵的低秩逼近，通过实证评估了样本抽样和投影方法的性能质量和运行时间，证明了它们的互补性，在相对误差较低前提下表明了不同采样方法之间的重要区别，并为随机抽样和随机投影方法提供最坏情况的理论边界。

    Mar, 2013

  • 通过自适应采样改进 CUR 矩阵分解和 Nyström 近似

    本文提出了更准确的基于列 / 行采样算法的 CUR 和 Nyström 算法，其期望相对误差较小，时间复杂度低且可以避免在 RAM 中存储整个数据矩阵，并对标准 Nyström 方法和 ensemble Nyström 方法的误差下限进行了理论分析，从而建立了一个更广泛的误差界限。

    Mar, 2013

  • 矩阵子集选择及应用的加速

    本文研究了一种矩阵的子集选择问题，其中关注了 Frobenius 范数和谱矩阵范数，并提出了多种新的逼近算法，并证明了在常数因子范围内逼近度是最优的，并且阐述了在一个无向图中找到低拉伸生成树的组合问题与矩阵子集选择问题之间的对应关系及其各种影响。

    Dec, 2011

  • 列子集选择、矩阵分解和特征值优化

    提出了一种基于随机列抽样的多项式时间算法，用于选择具有良好谱特性的矩阵子集，具有较高的计算效率和实用价值，并结合 Grothendieck 因子分解构造了一种新的近似算法，以计算矩阵的（无穷大，1）范数。

    Jun, 2008

  • 基于显式采样依赖的列子集选择谱误差界

    本文章研究了列子集选择的问题，通过分析随机化算法的谱范数重构，建立了一个新的、显式地以采样概率为依据的误差界，并通过解一个与误差界有关的约束优化问题来实现比传统采样分布更好的性能。数值模拟结果显示，新的采样分布可以比目前的算法在低秩矩阵近似和最小二乘近似方面表现得更好。

    May, 2015