Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

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$foreach$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$\mathrm{.}Thenfor$p \in [1,2]$,thegoalistofind$x \in $\mathbb{R}$^{d_1 \cdots d_q}$thatapproximatelyminimizes$|$\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))$,wherennz$(A_i)$isthenumberofnon-zeroentriesin$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))$\mathrm{.}Inthiswork,weprovidesignificantlyfasteralgorithms\mathrm{.}For$p=2$,ourrunningtimeis$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\mathrm{\parallel }\bar{A}x-\bar{b}{\mathrm{\parallel }}_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 $\mathrm{\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}$.