  In this work, we initiate the study of \emph{Dynamic Tensor Product
Regression}. One has matrices $A_1\in \mathbb{R}^{n_1\times d_1},\ldots,A_q\in
\mathbb{R}^{n_q\times d_q}$ and a label vector $b\in \mathbb{R}^{n_1\ldots
n_q}$, and the goal is to solve the regression problem with the design matrix
$A$ being the tensor product of the matrices $A_1, A_2, \dots, A_q$ i.e.
$\min_{x\in \mathbb{R}^{d_1\ldots d_q}}~\|(A_1\otimes \ldots\otimes
A_q)x-b\|_2$. At each time step, one matrix $A_i$ receives a sparse change, and
the goal is to maintain a sketch of the tensor product $A_1\otimes\ldots
\otimes A_q$ so that the regression solution can be updated quickly.
Recomputing the solution from scratch for each round is very slow and so it is
important to develop algorithms which can quickly update the solution with the
new design matrix. Our main result is a dynamic tree data structure where any
update to a single matrix can be propagated quickly throughout the tree. We
show that our data structure can be used to solve dynamic versions of not only
Tensor Product Regression, but also Tensor Product Spline regression (which is
a generalization of ridge regression) and for maintaining Low Rank
Approximations for the tensor product.
