超矩阵克罗内克积分解的部件最小二乘算法

《Journal of the Franklin Institute》：Component Least Square Algorithm for Kronecker Product Decomposition of Hypermatrices

　　

# 摘要

首先，提出了一种数值算法，称为分量最小二乘算法（CLSA），用于求解向量型超矩阵的最近Kronecker积（NKP）问题。利用该算法，有限和KPD问题也得到了解决。然后引入了置换矩阵。利用它，矩阵型超矩阵的KPD被转化为其等价的向量形式的KPD，随后CLSA也可应用于求解矩阵型超矩阵的同类问题。文中给出了一些数值例子以展示新算法，并将其与现有方法进行了比较。

# 引言

根据文献[1]，张量分解分别由文献[2]和[3]独立提出。该问题描述如下：设$\mathcal{A} = (a_{i_1,\cdots,i_d}) \in \mathbb{R}^{n_1 \times \cdots \times n_d}$为一个d阶超矩阵（也称为张量），维度为$n_1 \times \cdots \times n_d$。将其表示为如下分解形式[1]：

$$\mathcal{A} = \sum_{k=1}^{r} (x_{k_1} \otimes \cdots \otimes x_{k_d})$$

其中$x_{k_j} \in \mathbb{R}^{n_j}$，$j \in [1, d]$，$k \in [1, r]$。

最小的$r$称为$\mathcal{A}$的张量秩，记为$\text{rank}_t(\mathcal{A}) := \arg\min_r \{\text{分解(1)成立}\}$。

最近，该分解重新引起了广泛兴趣，因为它在网络化系统、信号处理、生成式人工智能（GAI）等许多新兴的大规模和数据密集型系统中有着广泛的应用。它也常被称为Kronecker积分解（KPD）[4]。

KPD的应用涵盖多个领域，例如：(a) 数值线性代数中的各类问题，参见文献[5]及其参考文献；(b) 逻辑动力系统的分析与综合[6]；(c) 医学成像数据分析[7]；(d) 图像处理与预处理[8]；(e) 交通和制造系统中的波达方向估计[9]、[10]；(f) 房间声学脉冲响应[11]；(g) 系统辨识[12]等。

特别是，KPD技术在人工智能中也找到了许多应用，因为它可以大大减少模型中的总参数数量。这对于大规模模型尤为重要。相关研究包括：(a) 为机器学习训练分块稀疏矩阵[13]；(b) GPT压缩[14]、[15]、[16]；(c) CNN压缩[17]；(d) 图像处理[18]等。

主要研究集中在基于奇异值分解（SVD）的矩阵KPD近似解[19]、[20]、[21]。此外，还提出了一些其他分解方法[8]、[22]。

在超矩阵的KPD方面也有一些研究工作[22]、[23]。

由(1)描述的KPD被称为Candecomp-Parafac（CP）分解[24]。在本文中，它也称为向量型超矩阵的KPD，因为在(1)中$\mathcal{A}$被视为向量，所有分解分量均为向量。

另一种形式的KPD是矩阵形式，描述如下：设$A \in \mathcal{M}_{m \times n}$，其中$m = \prod_{s=1}^{d} m_s$，$n = \prod_{s=1}^{d} n_s$。矩阵形式的KPD描述为[22]：

$$A = \sum_{k=1}^{r} A_{k_1} \otimes \cdots \otimes A_{k_d}$$

其中$A_{k_s} \in \mathcal{M}_{m_k \times n_k}$，$s \in [1, d]$，$k \in [1, r]$。

与KPD相关的问题是最近Kronecker积（NKP）问题，描述如下。设$A \in \mathcal{M}_{m \times n}$，其中$m = \prod_{s=1}^{d} m_s$，$n = \prod_{s=1}^{d} n_s$。NKP问题描述为[25]：求$A_s^*$，$s \in [1, d]$，使得

$$A \approx A_1^* \otimes \cdots \otimes A_d^*$$

其中$(A_1^*, \cdots, A_d^*) = \arg\min_{A_1, \cdots, A_d} \|A - A_1 \otimes \cdots \otimes A_d\|_F$。

显然，(3)是矩阵形式NKP，其对应的向量形式如下。设$\mathcal{A} \in \mathbb{R}^{n_1 \times \cdots \times n_d}$。求$x_s^* \in \mathbb{R}^{n_s}$，$s \in [1, d]$，使得

$$\mathcal{A} \approx \underset{s=1}{\overset{d}{\bigotimes}} x_s^*$$

其中$(x_1^*, \cdots, x_d^*) = \arg\min_{x_1, \cdots, x_d} \|\mathcal{A} - \underset{s=1}{\overset{d}{\bigotimes}} x_s\|_F$。

众所周知，最小和KPD（即关于张量秩的）是一个极具挑战性的问题[26]。

一个有趣的特例是精确KPD，即何存在$x_s^*$，$s \in [1, d]$，使得(4)（或对应的(3)）变为等式？

精确矩阵形式的KPD描述如下。对于给定的矩阵$A$，求$A_i$，$i \in [1, d]$，使得

$$A = A_1 \otimes A_2 \cdots \otimes A_d?$$

精确矩阵形式KPD存在两个长期未解决的公开问题：(i) 众所周知，矩阵的KPD不是唯一的，但这些分解之间如何关联。(ii) 矩阵何时可以精确分解为(5)的形式？

最近，对于向量形式分解，这两个问题由我们在文献[27]中首次解决。然后它们可以推广到矩阵形式分解如下：

对于(i)的解答是：如果$A = A_1 \otimes A_2 \cdots \otimes A_d = B_1 \otimes B_2 \cdots \otimes B_d$，则$B_i = \mu_i A_i$，$i \in [1, d]$，其中$\prod_{i=1}^{d} \mu_i = 1$。

对于(ii)，文献[27]中提出了一种称为首一分解算法（MDA）的算法。随后将看到，矩阵KPD可解当且仅当MDA提供了所有因子矩阵$A_i$，$i \in [1, d]$。

这两个问题的解决促使我们考虑一般的KPD问题。

本文的目的是开发一种数值算法，称为CLSA，用于求解NKP。该算法旨在寻找平方误差的驻点值，然后找到最小值。通过迭代使用NKP，我们最终可以得到有限和KPD。数值例子表明CLSA非常高效且精确。文中讨论了CLSA与基于奇异值分解相比的优缺点。

本文其余部分组织如下。第2节简要回顾了矩阵的半张量积（STP）。第3节讨论了超矩阵的矩阵化，然后介绍了现有分解方法；第4节考虑向量型超矩阵的KPD。首先考虑精确分解，回顾了MDA和基于MDA的必要充分条件。然后考虑NKP。作为本文的主要结果，提出了CLSA。最后，迭代使用CLSA得到有限和KPD。第5节首先引入置换矩阵。利用它，我们将矩阵型超矩阵的KPD转化为其等价向量形式的KPD。重新考虑了一个已知的数值例子以展示理论结果，并将CLSA与现有数值结果进行比较。最后，在第6节中给出一个简要的结论。

在本节结束之前，附上符号列表如下。

1. $\mathbb{R}^n$：$n$维实欧几里得空间。
2. $\mathbb{Z}^+$：正整数集。
3. $\mathcal{M}_{m \times n}$：$m \times n$矩阵集。
4. $\text{lcm}(a, b)$：$a$和$b$的最小公倍数。
5. $A \ltimes B$：$A$和$B$的半张量积。
6. $\mathbb{R}^{n_1 \times n_2 \times \cdots \times n_d}$：维度为$n_1 \times \cdots \times n_d$的$d$阶超矩阵。
7. $\mathbb{R}^{n_1 \ltimes n_2 \ltimes \cdots \ltimes n_d}$：维度为$n_1, n_2, \cdots, n_d$的$d$阶超向量。
8. $\mathcal{A}, \mathcal{B}$等：超矩阵。
9. $\vec{i} = I_d(i; n)$：索引$i \in [1, n]$。
10. $M_{\vec{j} \times \vec{k}}(\mathcal{A})$：$\mathcal{A}$的矩阵表示，其行由$\vec{j}$标记，列由$\vec{k}$标记。
11. $\text{Vr}(A)$（$\text{Vc}(A)$）：$A$的行堆叠形式（列堆叠形式）。
12. $[x]$：$x$的整数部分。
13. $[a, b]$：整数集合$a \leq i \leq b$。
14. $\delta_i^n$：单位矩阵$I_n$的第$i$列。
15. $\delta_n^{[i_1, \cdots, i_s]} := [\delta_{i_1}^n, \cdots, \delta_{i_s}^n]$。
16. $\mathbf{1}_\ell := (1, 1, \cdots, 1)^T$（$\ell$个1）。
17. $S_d$：$d$阶置换群。
18. $\otimes$：矩阵的Kronecker积。
19. $\ltimes$：矩阵的半张量积（STP）。

## 章节片段

### 矩阵的半张量积

本小节简要回顾矩阵的STP[28]。

**定义2.1** 设$A \in \mathcal{M}_{m \times n}$，$B \in \mathcal{M}_{p \times q}$，且$t = \text{lcm}(n, p)$。$A$和$B$的STP定义为

$$A \ltimes B = (A \otimes I_{t/n})(B \otimes I_{t/p})$$

STP是经典矩阵乘法的推广，即当$n = p$时，$A \ltimes B = AB$。因此，我们在大多数情况下省略符号$\ltimes$。

全文假设默认矩阵乘法为STP。

STP的一个重要优势是它保留了经典矩阵乘法的大部分性质。下文我们

### 超矩阵的矩阵化

**定义3.1**[29] 对于$n_1, \cdots, n_d \in \mathbb{Z}^+$，函数$f: [1, n_1] \times \cdots \times [1, n_d] \to \mathbb{R}$是一个d阶实超矩阵，维度为$n_1 \times \cdots \times n_d$。

等价地，超矩阵$\mathcal{A}$通常被视为由一组索引$i_s = [1, n_s]$，$s \in [1, d]$标记的一组有序数据。即，

$$\mathcal{A} = \{a_{i_1, i_d} | i_s = [1, n_s], s \in [1, d]\} \in \mathbb{R}^{n_1 \times \cdots \times n_d}$$

其中$\mathbb{R}^{n_1 \times \cdots \times n_d}$是d阶维度为$n_1 \times \cdots \times n_d$的超矩阵集合。

由于索引集在我们后续研究中起着重要作用，我们首先对索引集进行详细讨论

### 向量型超矩阵的精确KPD

**定义4.1** 给定超矩阵$\mathcal{A} = (a_{i_1, \cdots, i_d}) \in \mathbb{R}^{n_1 \times \cdots \times n_d}$。精确KPD意味着求$x_s \in \mathbb{R}^{n_s}$，$s \in [1, d]$，使得

$$V(\mathcal{A}) = \underset{s=1}{\overset{d}{\bigotimes}} x_s$$

假设$\mathcal{A}$给定，则$V := V(\mathcal{A}) \in \mathbb{R}^n$已知，其中$n = \prod_{s=1}^{d} n_s$。如果$V$被分解为$V = \underset{s=1}{\overset{d}{\bigotimes}} x_i$，利用命题3.13，所有头索引$e_s \doteq e(x_s)$均已知。

定义一组投影子为

$$\Xi_e^{[s, \mathbf{n}]} := \underset{r=1}{\overset{s-1}{\bigotimes}} [\delta_{e_r}^{n_r}]^T \otimes I_{n_s} \otimes \underset{r=s+1}{\overset{d}{\bigotimes}} [\delta_{e_r}^{n_r}]^T, \quad s \in [1, d]$$

其中$\mathbf{n} = n_1 \times \cdots \times n_d$。

然后我们有以下结果[27]、[30]，称为首一分解算法（MDA）。

**定理4.2** 设$V = V(\mathcal{A}) \in \mathbb{R}^n$。$V$及其

### 矩阵形式可分解性

假设$\mathcal{A} = (a_{i_1, \cdots, i_d}) \in \mathbb{R}^{n_1 \times \cdots \times n_d}$，$A = M_{\vec{j} \times \vec{k}}(\mathcal{A})$，其中$\vec{j} = \vec{i}_1 \vec{i}_2 \cdots \vec{i}_r$，$\vec{k} = \vec{i}_{r+1} \vec{i}_{r+2} \cdots \vec{i}_d$，$1 \leq r < d$。

设$p = \prod_{s=1}^{r} n_s$，$q = \prod_{s=r+1}^{d} n_s$，则$A = (a_{j,k}) \in \mathcal{M}_{p \times q}$。根据$\vec{j}$和$\vec{k}$的定义，显然$A$的行由索引$\vec{i}_1 \vec{i}_2 \cdots \vec{i}_r$标记，列由索引$\vec{i}_{r+1} \vec{i}_{r+2} \cdots \vec{i}_d$标记。

考虑$V = \text{Vr}(A)$。则显然$V$的元素由索引$\vec{i}_1 \vec{i}_2 \cdots \vec{i}_d$标记。

现在我们假设$d = 2r$为偶数，令索引划分如(37)所示，即设$\vec{j}_s = \vec{i}_s$，$\vec{k}_s = \vec{i}_{r+s}$，$s \in [1, r]$。

我们考虑

### 结论与备注

本文的主要贡献是提出了一种高效算法，称为CLSA，用于求解超矩阵的最小二乘近似。它具有明显的优势：(1) 线性计算复杂度；(2) 高精度；(3) 对阶数和维度无限制。与大多数优化算法类似，其主要缺点是算法可能达到一个驻点，该点仅是局部最小值，这取决于初始值的选择。由于计算的

### 未引用的参考文献

[33]、[34]、[35]、[36]、[37]

### CRediT作者贡献声明

戴赞成：原创草稿撰写。

### 利益冲突声明

作者声明不存在已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

戴赞成，1946年出生。清华大学毕业（1964-1970年），中国科学院研究生院硕士学位（1978-1981年），美国圣路易斯华盛顿大学博士学位（1981-1985年）。中国科学院数学与系统科学研究院教授（已退休），IEEE会士，IFAC会士，IFAC理事会成员（2011-2014年），IEEE CSS治理委员会成员（2010年和2015年），中国自动化学会控制理论专业委员会主任。

戴赞成