论文标题
动态张量产品回归
Dynamic Tensor Product Regression
论文作者
论文摘要
在这项工作中，我们启动了\ emph {动态张量产品回归}的研究。一个人具有矩阵$ a_1 \ in \ mathbb {r}^{n_1 \ times d_1}，\ ldots，a_q \ in \ mathbb {r}^{r}^{n_q \ times d_q} $和bailbb \ in \ in \ mathbb in \ mathbb in \ mathbb in \ mathbb in \ mathbb {解决设计矩阵$ a $的回归问题是矩阵$ a_1，a_2，\ dots，a_q $，即$ \ min_ {x \ in \ mathbb {r}^{r}^{d_1 \ ldots d_q}}} A_Q）X-B \ | _2 $。在每个时间步骤中，一个矩阵$ a_i $都会收到稀疏的更改，目标是保持张量产品的草图$ a_1 \ otimes \ ldots \ ldots \ otimes a_q $，以便可以快速更新回归解决方案。每轮从头开始重新计算解决方案非常慢，因此开发算法很重要，该算法可以快速使用新的设计矩阵更新解决方案。我们的主要结果是动态的树数据结构，其中任何对单个矩阵的更新都可以在整个树中迅速传播。我们表明，我们的数据结构可用于求解不仅张量产品回归的动态版本，还可以张紧产品样条回归（这是脊回归的概括）和维持张量产品的低等级近似值。
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.
