Skip to yearly menu bar Skip to main content


Poster

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

Huaian Diao · Rajesh Jayaram · Zhao Song · Wen Sun · David Woodruff

East Exhibition Hall B, C #53

Keywords: [ Algorithms ] [ Regression ] [ Components Analysis (e.g., CCA, ICA, LDA, PCA) ]


Abstract: We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Formally, given Ai\Rni×diAi\Rni×di for i=1,2,,qi=1,2,,q where nidinidi for each ii, and b\Rn1n2nqb\Rn1n2nq, let A=AiA2AqA=AiA2Aq. Then for p[1,2]p[1,2], the goal is to find x\Rd1dqx\Rd1dq that approximately minimizes AxbpAxbp. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker product A\Rn1nq×d1dqA\Rn1nq×d1dq. Specifically, for p=2p=2 they achieve a running time of O(qi=1nnz(Ai)+nnz(b)), where nnz(Ai) is the number of non-zero entries in Ai. Note that nnz(b) can be as large as Θ(n1nq). For p=1, q=2 and n1=n2, they achieve a worse bound of O(n3/21poly(d1d2)+nnz(b)). In this work, we provide significantly faster algorithms. For p=2, our running time is O(qi=1nnz(Ai)), which has no dependence on nnz(b). For p<2, our running time is O(qi=1nnz(Ai)+nnz(b)), which matches the prior best running time for p=2. We also consider the related all-pairs regression problem, where given A\Rn×d,b\Rn, we want to solve minx\RdˉAxˉbp, where ˉA\Rn2×d,ˉb\Rn2 consist of all pairwise differences of the rows of A,b. We give an O(nnz(A)) time algorithm for p[1,2], improving the Ω(n2) time required to form ˉA. Finally, we initiate the study of Kronecker product low rank and and low-trank approximation. For input A as above, we give O(qi=1nnz(Ai)) time algorithms, which is much faster than computing A.

Live content is unavailable. Log in and register to view live content