2022/10/08 by A. Rama Mohan Reddy, Reddy, Aravind, Zhao Song +3 · 3 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Parallel Computing and Optimization Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2210.03961
openalex publication_date 2022/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we initiate the study of Dynamic Tensor Product Regression. One has matrices A1∈ ℝn1× d1,…,Aq∈ ℝnq× dq and a label vector b∈ ℝn1… nq, and the goal is to solve the regression problem with the design matrix A being the tensor product of the matrices A1, A2, …, Aq i.e. minx∈ ℝd1… dq~‖(A1⊗ …⊗ Aq)x-b‖2. At each time step, one matrix Ai receives a sparse change, and the goal is to maintain a sketch of the tensor product A1⊗… ⊗ Aq 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.