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
]
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 ni≫dini≫di for each ii, and b∈\Rn1n2⋯nqb∈\Rn1n2⋯nq, let A=Ai⊗A2⊗⋯⊗AqA=Ai⊗A2⊗⋯⊗Aq. Then for p∈[1,2]p∈[1,2], the goal is to find x∈\Rd1⋯dqx∈\Rd1⋯dq that approximately minimizes ‖Ax−b‖p∥Ax−b∥p. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker product A∈\Rn1⋯nq×d1⋯dqA∈\Rn1⋯nq×d1⋯dq. 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 Θ(n1⋯nq). 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−ˉb‖p, 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