Jun, 2008

通信最优的并行和串行 QR 和 LU 因式分解：理论与实践

PDF
TL;DR本文介绍了一种并列的和依次的密集 QR 分解算法，既在它们所执行的通讯量上是最优的（高达多项式对数因子），也与 Householder QR 一样稳定。其中包括面向 m >> n 的一维（1-D）块循环行布局的 Tall Skinny QR（TSQR）算法，以及面向一般矩形矩阵的二维块循环布局分布的通信避免 QR（CAQR），每个块列分解调用 TSQR。
parallel algorithmssequential algorithmsdense qr factorizationcommunication-avoiding qrtall skinny qr
发现论文，激发创造
  • 通过随机低秩和低精度因式分解实现矩阵压缩

    我们提出一种算法，利用矩阵的低秩结构来获得任意矩阵的低秩分解，通过向量量化和压缩技术实现了压缩比例和逼近精度之间的折衷。

    Oct, 2023

  • 低秩矩阵分解的随机算法：尖锐性能界限

    本文研究文献中关于维数约减最常讨论的算法之一，即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人（2008）中算法的新颖分析方法，可以得出尖锐的估计和关于其性能的新见解。通过实验，我们证明了我们预测的紧密性与经验观测的一致性。

    Aug, 2013

  • 一种随机分块算法，用于高效计算矩阵排名披露因子分解

    本文介绍了一种计算部分秩相因分解的方法，该方法采用随机取样避免了列交换，从而使得计算速度得到了大幅提升，并且在各种矩阵上都表现出色，特别是在 GPU 结构上表现尤为突出。

    Mar, 2015

  • 通过流言算法实现矩阵完形填空的二维分解方法

    本研究提出了一种基于分布式学习的去中心化方法来分解稀疏矩阵为低密度矩阵，避免了中央服务器的需求，并在多个合成和真实数据集上验证了算法的性能。

    Nov, 2017

  • 矩阵低秩逼近的文献综述

    本文介绍了低秩逼近技术，并给出了众多相关技术的广泛参考资料。在此基础上，简要评述了基于奇异值分解、QR 分解、随机算法以及交叉 / 骨架逼近等各种低秩逼近技术的应用和优缺点。

    Jun, 2016

  • 快速线性代数是稳定的

    研究表明，许多快速递归矩阵乘法算法在范数意义下是稳定的，基本所有标准线性代数运算，包括 LU 分解、QR 分解、线性方程求解、矩阵求逆、最小二乘问题求解、特征值问题和奇异值分解等均可在 O（n^（ω+η））的时间复杂度内稳定地完成。

    Dec, 2006

  • 利用蝴蝶分解学习线性变换的快速算法

    通过将快速矩阵向量乘法的特性定义为稀疏矩阵的积，我们引入了一种分治方法的参数化形式，可以自动学习很多重要的变换的有效算法，并且在机器学习流水线中可以作为通用矩阵的轻量级替代，以学习高效且可压缩的变换。

    Mar, 2019

  • 利用随机性发现结构：构造近似矩阵分解的概率算法

    本文介绍了一种用于构建随机算法的模块化框架，以进行矩阵分解，通过随机抽样识别矩阵的大部分内容，并将输入矩阵压缩到子空间，这种方法在精度、速度和鲁棒性方面都比传统方法更具优势，能够更好地解决大数据集合的问题。

    Sep, 2009

  • 结构化低秩矩阵学习：算法与应用

    该论文提出了一种新的因子分解模型，它将低秩矩阵和线性子空间约束分离开来，从而使得优化问题在 Riemannian spectrahedron 流形上得以求解。实验证明，该方法在标准 / 鲁棒 / 非负矩阵补全，Hankel 矩阵学习和多任务学习等问题上具有较高的效率。

    Apr, 2017

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

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

    Jun, 2008