用 Cauchy 矩阵和多项式进行快速近似计算
本文提出一项新的算法,使用随机痕量估计方法,多项式逼近,以及快速系统求解器等高效地获得一个矩阵的奇异值谱的直方图,并用其来求解一类对称矩阵范数。同时,证明了精度高的算法可以在次立方时间内进行矩阵乘法,从而限制了计算有效电阻的难度。
Apr, 2017
论文证明了只有均匀分布于圆上的节点组成的范德蒙矩阵以外,大多数范德蒙矩阵都是病态的;此外,即便稍微改动圆上的节点,也会导致病态矩阵的出现,并分析了这种现象的原因,工具包括 Ekkart-Young 定理、Vandermonde-to-Cauchy 矩阵结构转换、基于 Cauchy 矩阵的新求逆公式和大型子矩阵的低秩逼近。
Apr, 2015
研究表明,许多快速递归矩阵乘法算法在范数意义下是稳定的,基本所有标准线性代数运算,包括 LU 分解、QR 分解、线性方程求解、矩阵求逆、最小二乘问题求解、特征值问题和奇异值分解等均可在 O(n^(ω+η))的时间复杂度内稳定地完成。
Dec, 2006
提供了快速算法,用于超约束的 ell_p 回归和相关问题,将问题减少到与输入矩阵的 coreset 相同的问题,我们还提供了一套用于通过椭球舍入找到良好条件的基础的改进结果,包括一种用于 ell_p 问题的快速子空间嵌入。
Jul, 2012
本文为矩阵缩放问题开发了多种有效的算法,并着重解决了一些特殊情况。该算法的复杂度为总复杂度 $\tilde {O}(m + n^{4/3})$,这比之前最好的精度 $\tilde {O}(n^4)$ 或 $O (m n^{1/2}/\varepsilon)$ 都要大大提高。
Apr, 2017
本研究提出一种简单而新颖的基于约束编程的方法,以查找快速矩阵乘法的非交换算法或提供不可行性证明。实验结果表明,我们可以在短时间内找到 $3 imes 3$ 的矩阵的快速矩阵乘法算法。
Jun, 2023
通过将快速矩阵向量乘法的特性定义为稀疏矩阵的积,我们引入了一种分治方法的参数化形式,可以自动学习很多重要的变换的有效算法,并且在机器学习流水线中可以作为通用矩阵的轻量级替代,以学习高效且可压缩的变换。
Mar, 2019
本文构建了一种快速算法来评估满足递推关系的函数族的转换,这些算法不仅包括在给定某些点的这些线性组合的值的情况下计算函数系数的算法,还包括反之亦然,在给定线性组合中的系数的情况下计算这些点的线性组合,这些过程也称为某些特殊函数级数的分析和合成。这篇论文中的算法是高效的,因为它们的计算成本与 n (ln n)(ln (1/epsilon))/^3 成正比,其中 n 是输入和输出数据量,epsilon 是计算精度。
Sep, 2006
探索使用次立方算法解决在线布尔矩阵向量乘法问题的困难程度,并将此问题与许多动态问题的困难程度联系起来,以展示它们之间的多项式时间困难性,并可能为它们展示深入的无条件下界或突破共同的障碍,并为一些未解决的问题提供了一个新的,统一的证明方法。
Nov, 2015