We propose the tensor Kronecker product singular value decomposition~(TKPSVD)
that decomposes a real $k$-way tensor $\mathcal{A}$ into a linear combination
of tensor Kronecker products with an arbitrary number of $d$ factors
$\mathcal{A} = \sum_{j=1}^R \sigma_j\, \mathcal{A}^{(d)}_j \otimes \cdots
\otimes \mathcal{A}^{(1)}_j$. We generalize the matrix Kronecker product to
tensors such that each factor $\mathcal{A}^{(i)}_j$ in the TKPSVD is a $k$-way
tensor. The algorithm relies on reshaping and permuting the original tensor
into a $d$-way tensor, after which a polyadic decomposition with orthogonal
rank-1 terms is computed. We prove that for many different structured tensors,
the Kronecker product factors $\mathcal{A}^{(1)}_j,\ldots,\mathcal{A}^{(d)}_j$
are guaranteed to inherit this structure. In addition, we introduce the new
notion of general symmetric tensors, which includes many different structures
such as symmetric, persymmetric, centrosymmetric, Toeplitz and Hankel tensors.

本文提出一种张量 Kronecker 积奇异值分解算法并引入了对称张量的新概念，该方法可以计算出具有结构的张量的 Kronecker 积因子，从而进行多种不同结构的张量分解。

张量的构造性任意阶 Kronecker 积分解

A constructive arbitrary-degree Kronecker product decomposition of  tensors

Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in
statistical learning of latent variable models and in data mining. In this
paper, we propose fast and randomized tensor CP decomposition algorithms based
on sketching. We build on the idea of count sketches, but introduce many novel
ideas which are unique to tensors. We develop novel methods for randomized
computation of tensor contractions via FFTs, without explicitly forming the
tensors. Such tensor contractions are encountered in decomposition methods such
as tensor power iterations and alternating least squares. We also design novel
colliding hashes for symmetric tensors to further save time in computing the
sketches. We then combine these sketching ideas with existing whitening and
tensor power iterative techniques to obtain the fastest algorithm on both
sparse and dense tensors. The quality of approximation under our method does
not depend on properties such as sparsity, uniformity of elements, etc. We
apply the method for topic modeling and obtain competitive results.

本文提出了一种基于草图的快速随机张量 CP 分解算法，通过 FFT 计算张量收缩并使用对称张量的冲突哈希进一步节省计算时间，结合白化和张量幂迭代技术，此算法在稀疏和密集张量上都具有最快的速度，适用于主题建模等应用。

通过草图实现快速和保证的张量分解

Fast and Guaranteed Tensor Decomposition via Sketching

We prove that multilinear (tensor) analogues of many efficiently computable
problems in numerical linear algebra are NP-hard. Our list here includes:
determining the feasibility of a system of bilinear equations, deciding whether
a 3-tensor possesses a given eigenvalue, singular value, or spectral norm;
approximating an eigenvalue, eigenvector, singular vector, or the spectral
norm; and determining the rank or best rank-1 approximation of a 3-tensor.
Furthermore, we show that restricting these problems to symmetric tensors does
not alleviate their NP-hardness. We also explain how deciding nonnegative
definiteness of a symmetric 4-tensor is NP-hard and how computing the
combinatorial hyperdeterminant of a 4-tensor is NP-, #P-, and VNP-hard. We
shall argue that our results provide another view of the boundary separating
the computational tractability of linear/convex problems from the
intractability of nonlinear/nonconvex ones.

证明了在数值线性代数中，许多高效可计算问题的多线性（张量）形式都是 NP 难的。其中包括决定一个双线性方程组的可行性，确定一个三阶张量是否具有给定的特征值，奇异值或谱范数；逼近特征值，特征向量，奇异向量或谱范数；确定三阶张量的秩或最佳秩 - 1 逼近等问题，以及证明了将这些问题限制在对称张量中并不能缓解它们的 NP 难度。通过证明 NP 难性，进一步指出了线性 / 凸问题计算可行性和非线性 / 非凸问题计算可行性之间的边界。