Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
复制标题
DOI：
10.1007/s10444-023-10061-z
复制
发表时间：
2021-04
影响因子：
1.7
通讯作者：
Yijun Dong;P. Martinsson
中科院分区：
文献类型：
--
作者：
Yijun Dong;P. Martinsson
像插值和CUR分解这样的矩阵分解提供了一个低秩近似的框架，其中选择给定矩阵的列和/或行的子集来形成其列和/或行空间的近似生成集。这种依赖于“自然”基的分解与传统的具有标准正交基的低秩分解相比具有几个优点，包括保留稀疏性或非负性等属性，维护数据中的语义信息，以及减少存储需求。矩阵分解可以使用经典的确定性算法来计算，例如列枢轴QR，它在实践中适用于小规模问题，但随着维度的增加，执行速度缓慢，并且容易受到对抗性输入的影响。最近，随机旋转方案引起了人们的广泛关注，因为它们已经被证明能够加快实际速度，在维度上具有很好的扩展性，有时也会导致更好的理论保证。这份手稿提供了一个比较研究的各种随机化的基于矩阵的旋转算法，利用经典的旋转方案作为积木。我们提出了一个通用的框架，封装这些随机化的基于递归的算法的共同结构，并提供了一个后验估计的框架误差界。此外，我们提出了一个新的具体化的一般框架，并数值证明其上级经验效率。
Matrix skeletonizations like the interpolative and CUR decompositions provide a framework for low-rank approximation in which subsets of a given matrix’s columns and/or rows are selected to form approximate spanning sets for its column and/or row space. Such decompositions that rely on “natural” bases have several advantages over traditional low-rank decompositions with orthonormal bases, including preserving properties like sparsity or non-negativity, maintaining semantic information in data, and reducing storage requirements. Matrix skeletonizations can be computed using classical deterministic algorithms such as column-pivoted QR, which work well for small-scale problems in practice, but suffer from slow execution as the dimension increases and can be vulnerable to adversarial inputs. More recently, randomized pivoting schemes have attracted much attention, as they have proven capable of accelerating practical speed, scale well with dimensionality, and sometimes also lead to better theoretical guarantees. This manuscript provides a comparative study of various randomized pivoting-based matrix skeletonization algorithms that leverage classical pivoting schemes as building blocks. We propose a general framework that encapsulates the common structure of these randomized pivoting-based algorithms and provides an a-posteriori-estimable error bound for the framework. Additionally, we propose a novel concretization of the general framework and numerically demonstrate its superior empirical efficiency.