标题： Kronecker乘积回归和低秩逼近的最优草图 显示英文标题

标题： Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

摘要： 我们研究Kronecker乘积回归问题，其中设计矩阵是两个或更多矩阵的Kronecker乘积。 给定$A_i \in \mathbb{R}^{n_i \times d_i}$对于$i=1,2,\dots,q$其中$n_i \gg d_i$对于每个$i$，以及$b \in \mathbb{R}^{n_1 n_2 \cdots n_q}$，令$\mathcal{A} = A_1 \otimes A_2 \otimes \cdots \otimes A_q$。 然后对于$p \in [1,2]$，目标是找到近似最小化$\|\mathcal{A}x - b\|_p$的$x \in \mathbb{R}^{d_1 \cdots d_q}$。 最近，Diao、Song、Sun 和 Woodruff（AISTATS，2018）给出了一种比构造 Kronecker 积更快的算法$\mathcal{A}$ 具体来说，对于$p=2$，其运行时间为$O(\sum_{i=1}^q \text{nnz}(A_i) + \text{nnz}(b))$，其中 nnz$(A_i)$是$A_i$中非零条目的数量。 注意，nnz$(b)$可以高达$n_1 \cdots n_q$。 对于$p=1,$ $q=2$ 和$n_1 = n_2$，它们获得了一个更差的界$O(n_1^{3/2} \text{poly}(d_1d_2) + \text{nnz}(b))$。 在本工作中，我们提供了显著更快的算法。 对于$p=2$，我们的运行时间是$O(\sum_{i=1}^q \text{nnz}(A_i) )$，其不依赖于 nnz$(b)$。 对于$p<2$，我们的运行时间是$O(\sum_{i=1}^q \text{nnz}(A_i) + \text{nnz}(b))$，这与之前对于$p=2$的最佳运行时间相匹配。 我们还考虑了相关的所有对回归问题，其中给定$A \in \mathbb{R}^{n \times d}, b \in \mathbb{R}^n$，我们想要求解$\min_{x} \|\bar{A}x - \bar{b}\|_p$，其中$\bar{A} \in \mathbb{R}^{n^2 \times d}, \bar{b} \in \mathbb{R}^{n^2}$包含$A,b$行的所有成对差值。 我们给出一个$O(\text{nnz}(A))$时间算法用于$p \in[1,2]$，改进了形成$\bar{A}$所需的$\Omega(n^2)$时间。 最后，我们开始研究Kronecker积低秩和低$t$-秩逼近。 对于输入$\mathcal{A}$如上，我们给出$O(\sum_{i=1}^q \text{nnz}(A_i))$时间算法，这比计算$\mathcal{A}$快得多。 显示英文摘要

摘要： We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Given $A_i \in \mathbb{R}^{n_i \times d_i}$ for $i=1,2,\dots,q$ where $n_i \gg d_i$ for each $i$, and $b \in \mathbb{R}^{n_1 n_2 \cdots n_q}$, let $\mathcal{A} = A_1 \otimes A_2 \otimes \cdots \otimes A_q$. Then for $p \in [1,2]$, the goal is to find $x \in \mathbb{R}^{d_1 \cdots d_q}$ that approximately minimizes $\|\mathcal{A}x - b\|_p$. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker product $\mathcal{A}$ Specifically, for $p=2$ their running time is $O(\sum_{i=1}^q \text{nnz}(A_i) + \text{nnz}(b))$, where nnz$(A_i)$ is the number of non-zero entries in $A_i$. Note that nnz$(b)$ can be as large as $n_1 \cdots n_q$. For $p=1,$ $q=2$ and $n_1 = n_2$, they achieve a worse bound of $O(n_1^{3/2} \text{poly}(d_1d_2) + \text{nnz}(b))$. In this work, we provide significantly faster algorithms. For $p=2$, our running time is $O(\sum_{i=1}^q \text{nnz}(A_i) )$, which has no dependence on nnz$(b)$. For $p<2$, our running time is $O(\sum_{i=1}^q \text{nnz}(A_i) + \text{nnz}(b))$, which matches the prior best running time for $p=2$. We also consider the related all-pairs regression problem, where given $A \in \mathbb{R}^{n \times d}, b \in \mathbb{R}^n$, we want to solve $\min_{x} \|\bar{A}x - \bar{b}\|_p$, where $\bar{A} \in \mathbb{R}^{n^2 \times d}, \bar{b} \in \mathbb{R}^{n^2}$ consist of all pairwise differences of the rows of $A,b$. We give an $O(\text{nnz}(A))$ time algorithm for $p \in[1,2]$, improving the $\Omega(n^2)$ time needed to form $\bar{A}$. Finally, we initiate the study of Kronecker product low rank and low $t$-rank approximation. For input $\mathcal{A}$ as above, we give $O(\sum_{i=1}^q \text{nnz}(A_i))$ time algorithms, which is much faster than computing $\mathcal{A}$.