论文标题
次级kronecker回归，并应用于张量分解
Subquadratic Kronecker Regression with Applications to Tensor Decomposition
论文作者
论文摘要
Kronecker回归是一个高度结构的最小二乘问题$ \ min _ {\ MathBf {X}}} \ lvert \ Mathbf {k} \ Mathbf {x} - \ MathBf {b} \ rvert_ \ rvert_ {2}^2 $ \ Mathbf {a}^{（1）} \ otimes \ cdots \ otimes \ Mathbf {a}^{（n）} $是因子矩阵的Kronecker产品。在广泛使用的最小二乘（ALS）算法的每个步骤中都出现了这种回归问题，用于计算张量的塔克分解。我们介绍了第一个用于求解Kronecker回归的子次数算法，以避免在运行时间中避免指数项$ o（\ varepsilon^{ - n}）$的$（1+ \ varepsilon）$ - 近似值。我们的技术结合了杠杆评分抽样和迭代方法。通过扩展我们的块设计矩阵的方法，其中一个块是Kronecker产品，我们还实现了（1）Kronecker Ridge回归和（2）更新ALS中Tucker Demotition的因子矩阵的次级时间算法，这并不是纯Kronecker回归问题，从而改善了所有步骤的alser als als als als alserer alserer alsererer的运行时间。我们演示了该Kronecker回归算法在合成数据和现实世界图像张量上的速度和准确性。
Kronecker regression is a highly-structured least squares problem $\min_{\mathbf{x}} \lVert \mathbf{K}\mathbf{x} - \mathbf{b} \rVert_{2}^2$, where the design matrix $\mathbf{K} = \mathbf{A}^{(1)} \otimes \cdots \otimes \mathbf{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+\varepsilon)$-approximation that avoids the exponential term $O(\varepsilon^{-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.
