Subquadratic Kronecker Regression with Applications to Tensor Decomposition

Author name not available (Why is that?)

Publication date: 11 September 2022

Abstract: Kronecker regression is a highly-structured least squares problem

m i n_{m a t h b f x} l V e r t m a t h b f K m a t h b f x - m a t h b f b V e r t_{2}^{2}

, where the design matrix

m a t h b f K = m a t h b f A^{(1)} o t i m e s c d o t s o t i m e s m a t h b f A^{(N)}

is a Kronecker product of factor matrices. This regression problem arises in each step of the widely-used alternating least squares (ALS) algorithm for computing the Tucker decomposition of a tensor. We present the first subquadratic-time algorithm for solving Kronecker regression to a

(1 + v a r e p s i l o n)

-approximation that avoids the exponential term

O (v a r e p s i l o n^{- N})

in the running time. Our techniques combine leverage score sampling and iterative methods. By extending our approach to block-design matrices where one block is a Kronecker product, we also achieve subquadratic-time algorithms for (1) Kronecker ridge regression and (2) updating the factor matrices of a Tucker decomposition in ALS, which is not a pure Kronecker regression problem, thereby improving the running time of all steps of Tucker ALS. We demonstrate the speed and accuracy of this Kronecker regression algorithm on synthetic data and real-world image tensors.

Has companion code repository: https://github.com/fahrbach/subquadratic-kronecker-regression

Mathematics Subject Classification ID

No records found.

This page was built for publication: Subquadratic Kronecker Regression with Applications to Tensor Decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6410344)