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

Dec, 2008

An Improved Approximation Algorithm for the Column Subset Selection Problem

Christos Boutsidis, Michael W. Mahoney, Petros Drineas

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

Abstract

We consider the problem of selecting the best subset of exactly $k$ columns from an $m \times n$ matrix $A$. We present and analyze a novel two-stage algorithm that runs in $O(\min\{mn^2,m^2n\})$ time and returns as output an $m \times k$ matrix $C$ consisting of exactly $k$ columns of

column subset selection problem probability distribution frobenius norm spectral norm algorithm

发现论文，激发创造

列子集选择是 NP 完备问题

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

Jan, 2017

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

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

Dec, 2011

基于列的最优低秩矩阵重构

证明对于任意实值矩阵 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

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

本文提出了利用数据矩阵的谱属性来获得改进的逼近保证，超越了标准的最坏情况分析，研究结果显示：逼近因子作为 k 的函数可能会呈现多个波峰和波谷，这被称为多峰曲线。

Feb, 2020

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

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

Jun, 2008

广义列子集选择的快速贪心算法

本文定义了一般化的列子集选择问题，该问题涉及从源矩阵 A 中选择少量列，这些列最能逼近目标矩阵 B 的跨度，提出了一种快速贪心算法来解决这个问题，并与可以使用所提出的算法有效解决的不同问题建立联系。

Dec, 2013

公平列子集选择

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

Jun, 2023

大矩阵取样：一种基于几何函数分析的方法

通过研究矩阵的随机子矩阵，证明了用最小可能 O（rlogr）的随机子矩阵（其中 r 是矩阵的数值秩），可以近似计算其谱范数，并给出了在该领域中的最优保证，并使用概率论的方法。Banach 空间中的操作型随机变量的大数定律证明了其工作原理。

Mar, 2005

行 / 列子集选择的高效体积抽样

通过选择相应的行，并按照其自身以及原点形成的单形的体积进行概率比例采样，给出了有效的算法。这些算法解决了 Kannan 和 Vempala 的有关谱算法的专著中的一个问题，并且还对低秩矩阵逼近提供了几个有趣的结果。

Apr, 2010

稳定秩下的最优近似矩阵乘积

用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

Jul, 2015