Apr, 2017

矩阵缩放的更快算法

PDF
TL;DR本文为矩阵缩放问题开发了多种有效的算法，并着重解决了一些特殊情况。该算法的复杂度为总复杂度 $\tilde {O}(m + n^{4/3})$，这比之前最好的精度 $\tilde {O}(n^4)$ 或 $O (m n^{1/2}/\varepsilon)$ 都要大大提高。
matrix scalingdiagonal matricesdoubly stochasticcontinuous optimizationpermanent approximation
发现论文，激发创造
  • 基于盒约束牛顿法和内点方法的矩阵缩放和平衡

    本篇论文提出了一种新的二阶优化框架，用于处理矩阵缩放和平衡问题，提出了可以忽略对数因子的算法，可以在几乎线性时间内解决这些问题，同时提供了一种使用内部点方法的单独算法，以及广泛适用的第二阶鲁棒函数最小化方法。

    Apr, 2017

  • 高效求解密集线性系统的方法

    提出了一种随机优化算法，通过块坐标下降方法和矩阵草图技术，在线性系统中实现了良好的收敛性能和快速迭代时间。

    Dec, 2023

  • 对称、对角占优线性系统预处理和求解的几乎线性时间算法

    提出一种基于随机算法、适用于对称矩阵的预处理方法及线性系统求解器，其具低渐进复杂度；该算法中，递归运用子图预处理器来改进 Vaidya（1990）的子图预处理方法，当矩阵的非零结构为平面图时，求解器可以期望在时间 O（nlog²n + nlognloglognlog (1/ε)）内运行。

    Jul, 2006

  • SDD 线性系统的近乎 O (mlogn) 求解器

    提出了一种针对对称对角占优线性系统的改进算法，该算法利用图稀疏化和预处理来构建一条链以求解方程。同时，也介绍了一种构建近似最小 “拉伸” 生成树的算法，并证明了这两个算法的时间效率。

    Feb, 2011

  • 快速线性代数是稳定的

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

    Dec, 2006

  • 矩阵游戏的协调方法

    本文提出基于 primal-dual coordinate 方法，并应用于解决包含线性规划、分类和回归问题的双线性鞍点问题。通过设计高效的数据结构和低方差梯度估计器，我们获得了近乎恒定的每次迭代复杂度，并且在采样复杂度上实现了改进。同时，我们应用该方法到最小圆覆盖，最大内接圆和线性回归的计算几何问题中，并获得了改善的计算复杂度。

    Sep, 2020

  • 如何伪造由高斯矩阵相乘

    本研究提出了新的随机化矩阵转换方法，用以快速计算矩阵乘法并保证计算效率，可以应用于非负矩阵分解和支持向量机等计算任务中。

    Jun, 2016

  • 稠密矩阵的量子线性系统算法

    介绍了一个基于奇异值估算子程序的量子算法，可解决线性方程组问题，其运行时间与矩阵 A 的条件数、Frobenius 范数和精度参数有关。当应用于具有范数受到限制的密集矩阵时，所提出的算法的运行时间受到限制，其运行时间比已知的量子线性系统算法提高了平方级别。

    Apr, 2017

  • 矩阵缩放与 Sinkhorn 正常形式在矩阵和正态映射中的应用综述

    通过在非负矩阵 $A$ 内找到对角矩阵 $D_1,~D_2$，可以得到 $D_1AD_2$ 是双重随机的 Sinkhorn 定理，这篇文章评述了 70 多年来的矩阵缩放，重点关注围绕该问题及其解决方案的数学领域以及扩展至矩阵代数之间的正态映射，几乎不包含任何不普遍的未发表结果。

    Sep, 2016

  • 解决 SDD 系统逼近最优解

    本研究介绍了一种基于递增稀疏化的算法，可在输入 n 个顶点和 m 条边的加权图以及一个值 k 后，产生一个有限边数为 n-1+m/k 的递增稀疏化图，较好地维持了图的条件数，并以很快的速度求解出满足一定误差要求的向量，这一算法基于 Chebyshev 迭代和递归算法实现。

    Mar, 2010