论文标题
当前矩阵乘法时间中线性代数的最佳算法
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
论文作者
论文摘要
我们研究线性代数的基本问题，例如找到行的最大线性独立子集（基础），求解线性回归或计算子空间嵌入。对于这些问题，我们将输入矩阵$ \ mathbf {a} \ in \ mathbb {r}^{n \ times d} $带有$ n> d $。可以用$ \ text {nnz}（\ mathbf {a}）$时间读取输入，该$表示$ \ mathbf {a} $的非零条目的数量。在本文中，我们表明，除了读取输入矩阵所需的时间之外，这些基本线性代数问题可以在$ d^ω$时间（即$ω\ 2.37 $是当前的矩阵 - multiplication endentent）中解决。 为此，我们介绍了一个恒定的因子子空间嵌入，其中最佳$ M = \ Mathcal {o}（d）$行数，并且可以在时间$ \ Mathcal {o} \ left（\ frac {\ frac {\ frac {\ frac {\ text {nnz}（nnz}（nnz}（a}（a a}））\ a {a a}）对于任何权衡参数$α> 0 $，α} \ text {poly}（\ log d）$，收紧了Chepurko et的最新结果。 al。 [SODA 2022]可以实现$ \ exp（\ text {poly}（\ log \ log \ log n））$变形，$ m = d \ cdot \ text {poly}（\ log log \ log \ log \ log \ log d）$行$ \ MATHCAL {O} \ left（\ frac {\ text {nnz}（\ Mathbf {a}）}α+d^{2+α+o（1）} \ right）$时间。我们的子空间嵌入使用了最近显示的堆叠子采样的随机hadamard变换（SRHT）的属性，实际上增加了输入维度，以“扩散”大量坐标中输入矢量的质量，然后进行随机采样。为了控制随机抽样的效果，我们使用快速的半决赛编程来重新持续行。然后，我们使用常数因子子空间嵌入来提供第一个最佳运行时算法，以查找列，回归和利用分数采样的最大线性独立子集。为此，我们还介绍了一种新颖的子例程，它迭代地生长了一组独立的行，这可能具有独立的兴趣。
We study fundamental problems in linear algebra, such as finding a maximal linearly independent subset of rows or columns (a basis), solving linear regression, or computing a subspace embedding. For these problems, we consider input matrices $\mathbf{A}\in\mathbb{R}^{n\times d}$ with $n > d$. The input can be read in $\text{nnz}(\mathbf{A})$ time, which denotes the number of nonzero entries of $\mathbf{A}$. In this paper, we show that beyond the time required to read the input matrix, these fundamental linear algebra problems can be solved in $d^ω$ time, i.e., where $ω\approx 2.37$ is the current matrix-multiplication exponent. To do so, we introduce a constant-factor subspace embedding with the optimal $m=\mathcal{O}(d)$ number of rows, and which can be applied in time $\mathcal{O}\left(\frac{\text{nnz}(\mathbf{A})}α\right) + d^{2 + α}\text{poly}(\log d)$ for any trade-off parameter $α>0$, tightening a recent result by Chepurko et. al. [SODA 2022] that achieves an $\exp(\text{poly}(\log\log n))$ distortion with $m=d\cdot\text{poly}(\log\log d)$ rows in $\mathcal{O}\left(\frac{\text{nnz}(\mathbf{A})}α+d^{2+α+o(1)}\right)$ time. Our subspace embedding uses a recently shown property of stacked Subsampled Randomized Hadamard Transforms (SRHT), which actually increase the input dimension, to "spread" the mass of an input vector among a large number of coordinates, followed by random sampling. To control the effects of random sampling, we use fast semidefinite programming to reweight the rows. We then use our constant-factor subspace embedding to give the first optimal runtime algorithms for finding a maximal linearly independent subset of columns, regression, and leverage score sampling. To do so, we also introduce a novel subroutine that iteratively grows a set of independent rows, which may be of independent interest.
