Near optimal sketching of low-rank tensor regression

We study the least squares regression problem (Equation Presented) where ⊙ is a low-rank tensor, defined as ⊙ = Σ^R_r=1 θ₁^(r)o ⋯ o θ^(r)_D, for vectors θ^(r)_d ϵ ℝ^pd for all r ϵ [R] and d ϵ [D]. Here, o denotes the outer product of vectors, and A(⊙) is a linear function on ⊙. This problem is motivated by the fact that the number of parameters in ⊙ is only R · Σ^D_d=1pd, which is significantly smaller than the Π^D_d=1pd number of parameters in ordinary least squares regression. We consider the above CP decomposition model of tensors ⊙, as well as the Tucker decomposition. For both models we show how to apply data dimensionality reduction techniques based on sparse random projections Φ ϵ ℝ^m×n with m << n, to reduce the problem to a much smaller problem min ⊙ ∥ΦA(⊙) - Φb∥²₂, for which ∥ΦA(⊙)-Φb∥²₂ = (1±ϵ)∥A(⊙)-b∥²₂ holds simultaneously for all ⊙. We obtain a significantly smaller dimension and sparsity in the randomized linear mapping Φ than is possible for ordinary least squares regression. Finally, we give a number of numerical simulations supporting our theory.