Feb, 2016

Cholesky 分解的求导

PDF
TL;DR本文针对矩阵计算中的不同策略进行了研究，并推导了包含 Cholesky 分解的表达式的符号和算法更新规则。我们建议使用新的 “blocked” 算法，基于 LAPACK 库中的 Cholesky 算法 DPOTRF 进行微分，该算法使用来自 BLAS 的 “Level 3” 矩阵 - 矩阵操作，易于进行缓存友好和并行化。对于大矩阵，得到的算法是计算 Cholesky 导数的最快方式，并且比通常使用的算法快一个数量级。在某些计算环境中，基于符号推导的更新对于小矩阵而言比基于微分 Cholesky 算法的更新快。符号和算法方法可以结合起来以获得最佳效果。
matrix-based computationscholesky decompositionblocked algorithmscache-friendlyparallelize
发现论文，激发创造
  • 自动求导的线性代数

    介绍了如何将一些矩阵分解运算（如 Cholesky、LQ 和对称特征值分解）实现为可微分操作符，并将其在 MXNet 上实现。这使得许多基本的机器学习原语（如高斯过程、最小二乘估计、主成分分析和卡尔曼平滑）易于实现并与深度神经网络（DNN）相结合，优化效率和运行时间。

    Oct, 2017

  • 关于 Bareiss 和相关 Toeplitz 分解算法的稳定性

    对位移秩为 2 的对称正定矩阵的 Cholesky 分解算法进行了数值稳定性分析，得出 Bareiss 算法稳定，而 Levinson 算法在反射系数不全为正时并不稳定，实验结果表明 Bareiss 算法的残差要比 Levinson 算法小。

    Apr, 2010

  • 大矩阵的函数梯度

    通过导出 Lanczos 和 Arnoldi 迭代的未知共轭系统，该研究利用 JAX 实现了用于科学机器学习模型的数值线性代数效率高的可微分算法，该算法成功地不需要特定问题的代码优化，并在不同领域如选取高斯过程模型和校准贝叶斯神经网络中表现出与其他常见方法相当甚至更好的效果。

    May, 2024

  • 快速可导的矩阵平方根

    本文提出了两种用于计算矩阵可区分平方根的更加高效的变体，分别采用矩阵泰勒多项式和矩阵帕德逼近法进行前向传播，并使用连续时钟李亚普诺夫方程的渐进求解来计算后向梯度，表明两种方法在各种任务上比现有方法速度更快，且能够实现更好的性能，例如 decorrelated batch normalization 和 second-order vision transformer。

    Jan, 2022

  • 矩阵对角化和奇异值分解：静态 SageMath 和动态 ChatGPT 并置

    研究生在学习线性代数时通常会遇到的难点及解决方式，包括使用免费计算机代数系统 SageMath 处理需要算法思维技能的问题，如对角化和奇异值分解，并通过 ChatGPT 提高计算能力和批判性思维。

    Mar, 2023

  • 基于稀疏化 Cholesky 和 Multigrid 求解器的 Connection Laplacians

    本文介绍了稀疏 Cholesky 分解和稀疏多重网格算法用于解决线性方程组的问题，并使用这些新算法推导出第一个解决图像和信号处理中 Laplacian 矩阵广泛应用的连接 Laplacian 线性时间算法，并证明每个连接 Laplacian 都有一个线性规模的近似逆矩阵。

    Dec, 2015

  • 多层 Toeplitz 矩阵的 Vandermonde 分解及其在多维超分辨率中的应用

    本文介绍了 Toeplitz 矩阵的 Vandermonde 分解在多维频率估计中的应用，其方法包括了基于松弛技术的实用算法以及标准化的原子 $l_0$ 范数公式。

    May, 2015

  • 优化层交替微分

    本文提出了一种名为 Alt-Diff 的新框架，该框架将优化问题嵌入深度神经网络并快速递归求导，以提高计算速度。实验证明， Alt-Diff 在更少的时间内提供了与现有先进技术可比较的结果。

    Oct, 2022

  • 三阶张量的规范多项式分解：简化到广义特征值分解

    本文提出了一种代数算法来计算不具有完整列秩的张量的标准分解（CPD），只要满足著名的 Kruskal 条件，就可以通过代数方式找到 CPD。

    Dec, 2013

  • 用 Cauchy 矩阵和多项式进行快速近似计算

    本文提出了一种新的数字算法，该算法使用快速多极法来加速多点多项式求值和插值问题的解决，以实现近乎线性的时间。

    Jun, 2015