Near Optimal Sketching of Low-Rank Tensor Regression

Abstract

We study the least squares regression problem \begin{align*} \min_{Θ\in \mathcal{S}_{\odot D,R}} \|AΘ-b\|_2, \end{align*} where ${\mathcal{S}}_{\odot D,R}$ is the set of $\Theta$ for which $\Theta ={\sum }_{r=1}^R{\theta }_1^{(r)}\circ \cdots \circ {\theta }_D^{(r)}$ for vectors ${\theta }_d^{(r)}\in {\mathbb{R}}^{p_d}$ for all $r\in [R]$ and $d\in [D]$, and $\circ$ denotes the outer product of vectors. That is, $\Theta$ is a low-dimensional, low-rank tensor. This is motivated by the fact that the number of parameters in $\Theta$ is only $R\cdot {\sum }_{d=1}^D{p}_d$, which is significantly smaller than the ${\prod }_{d=1}^D{p}_d$ number of parameters in ordinary least squares regression. We consider the above CP decomposition model of tensors $\Theta$, as well as the Tucker decomposition. For both models we show how to apply data dimensionality reduction techniques based on {\it sparse} random projections $\Phi \in {\mathbb{R}}^{m\times n}$, with $m\ll n$, to reduce the problem to a much smaller problem ${\min }_{\Theta }\Vert \Phi A\Theta -\Phi b{\Vert }_2$, for which if ${\Theta }^{\prime }$ is a near-optimum to the smaller problem, then it is also a near optimum to the original problem. We obtain significantly smaller dimension and sparsity in $\Phi$ than is possible for ordinary least squares regression, and we also provide a number of numerical simulations supporting our theory.

36 pages, 2 figures, 2 tables, Accepted at NIPS 2017

References in corpus (1)

• Tucker Tensor Regression and Neuroimaging Analysis