张量补充 2 （补充ing）

数学概念

1. 张量 (Tensor)

• 定义: 张量是多维数组的通用表示，表示为 $\mathcal{X}\in {\mathbb{R}}^{I_1\times I_2\times \cdots \times I_N}$，其中 $I_1,I_2,\dots ,I_N$ 是各个维度的大小。
• 阶数 (Order): 张量的阶数是它的维度数，例如一阶张量是向量，二阶张量是矩阵，三阶或更高阶的张量则称为高阶张量。

2. CANDECOMP/PARAFAC (CP) 分解

• 定义: CP分解是一种将张量分解为秩为一的张量之和的分解方式。

• 秩 (Rank): 张量的秩是分解成秩为一张量之和所需的最小数量。

• 表示: 对于三阶张量 $\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，CP分解表示为

  $$\mathcal{X}\approx \sum _{r=1}^R{\lambda }_r{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r$$

  其中，$R$ 是秩，${\lambda }_r$ 是标量，${\mathbf{a}}_r$，${\mathbf{b}}_r$，${\mathbf{c}}_r$ 分别是列向量。

3. 外积 (Outer Product)

• 定义: 外积是两个向量之间的操作，结果是一个张量。例如，两个向量 $\mathbf{a}$ 和 $\mathbf{b}$ 的外积 $\mathbf{a}\circ \mathbf{b}$ 是一个矩阵，其中每个元素是 $\mathbf{a}$ 和 $\mathbf{b}$ 的对应元素的乘积。

4. Khatri-Rao 积 (Khatri-Rao Product)

• 定义: Khatri-Rao积是两个矩阵的列间Kronecker积。例如，矩阵 $\mathbf{A}\in {\mathbb{R}}^{I\times K}$ 和 $\mathbf{B}\in {\mathbb{R}}^{J\times K}$ 的Khatri-Rao积定义为

  $$\mathbf{A}\odot \mathbf{B}=[{\mathbf{a}}_1\otimes {\mathbf{b}}_1,{\mathbf{a}}_2\otimes {\mathbf{b}}_2,\dots ,{\mathbf{a}}_K\otimes {\mathbf{b}}_K]$$

  其中 $\otimes$ 表示Kronecker积，${\mathbf{a}}_i$ 和 ${\mathbf{b}}_i$ 是 $\mathbf{A}$ 和 $\mathbf{B}$ 的第 $i$ 列。

5. 秩 (Rank)

• 定义: 张量的秩是可以表示该张量的秩为一的张量个数的最小值。对于矩阵，这是行或列的最大线性无关数。

• 公式:

  $$\text{rank}(\mathcal{X})=\min \left\{R:\mathcal{X}=\sum _{r=1}^R{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r\right\}$$

6. 边界秩 (Border Rank)

• 定义: 边界秩是通过近似表示一个张量的秩的最小值。换句话说，它是通过对张量进行近似得到的最小秩。

• 公式:

  rank ~ ( X ) = min ⁡ { r ∣ 对于任意  ϵ > 0 , 存在张量  E , 使得  ∥ E ∥ < ϵ 且 rank ( X + E ) = r } \tilde{\text{rank}}(\mathcal{X}) = \min \left\{ r \mid \text{对于任意 } \epsilon > 0, \text{ 存在张量 } \mathcal{E}, \text{使得 } \|\mathcal{E}\| < \epsilon \text{ 且 } \text{rank}(\mathcal{X} + \mathcal{E}) = r \right\} rank~(X)=min{r∣对于任意 ϵ>0, 存在张量 E,使得 ∥E∥<ϵ 且 rank(X+E)=r}

7. 交替最小二乘法 (Alternating Least Squares, ALS)

• 定义: ALS是一种迭代算法，通过固定其他因子矩阵，逐步优化某一个因子矩阵，使得损失函数逐渐减小，从而逼近最优解。
• 算法步骤:

  • 固定矩阵 $\mathbf{B},\mathbf{C}$，求解 $\mathbf{A}$：

    $$\mathbf{A}\leftarrow {\mathbf{X}}_{(1)}(\mathbf{C}\odot \mathbf{B}){\left[({\mathbf{C}}^T\mathbf{C})\ast ({\mathbf{B}}^T\mathbf{B})\right]}^{-1}$$

  • 固定矩阵 $\mathbf{A},\mathbf{C}$，求解 $\mathbf{B}$：

    $$\mathbf{B}\leftarrow {\mathbf{X}}_{(2)}(\mathbf{C}\odot \mathbf{A}){\left[({\mathbf{C}}^T\mathbf{C})\ast ({\mathbf{A}}^T\mathbf{A})\right]}^{-1}$$

  • 固定矩阵 $\mathbf{A},\mathbf{B}$，求解 $\mathbf{C}$：

    $$\mathbf{C}\leftarrow {\mathbf{X}}_{(3)}(\mathbf{B}\odot \mathbf{A}){\left[({\mathbf{B}}^T\mathbf{B})\ast ({\mathbf{A}}^T\mathbf{A})\right]}^{-1}$$

CANDECOMP/PARAFAC (CP) 分解

CP分解是一种将张量表示为多个秩为一的张量的和的分解方式。对于一个三阶张量 $\mathcal{X}\in {\mathbb{R}}^{I\times J\times K}$，CP分解的形式如下：

$$\mathcal{X}\approx \sum _{r=1}^R{\lambda }_r{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r$$

其中，$R$ 是分解的秩，${\lambda }_r$ 是标量，${\mathbf{a}}_r\in {\mathbb{R}}^I$，${\mathbf{b}}_r\in {\mathbb{R}}^J$，${\mathbf{c}}_r\in {\mathbb{R}}^K$ 是对应的因子矩阵，$\circ$ 表示外积。

矩阵化的形式为：

$${\mathbf{X}}_{(1)}\approx \mathbf{A}(\mathbf{C}\odot \mathbf{B}{)}^T$$

$${\mathbf{X}}_{(2)}\approx \mathbf{B}(\mathbf{C}\odot \mathbf{A}{)}^T$$

$${\mathbf{X}}_{(3)}\approx \mathbf{C}(\mathbf{B}\odot \mathbf{A}{)}^T$$

这里 $\odot$ 表示Khatri-Rao积。

张量秩

张量的秩（Rank）定义为能将张量表示为秩为一的张量之和的最小数量。具体而言，对于张量 $\mathcal{X}$，其秩为：

$$\text{rank}(\mathcal{X})=\min \left\{R:\mathcal{X}=\sum _{r=1}^R{\mathbf{a}}_r\circ {\mathbf{b}}_r\circ {\mathbf{c}}_r\right\}$$

张量秩的计算非常复杂，一般无法通过简单算法确定。

边界秩（Border Rank）

边界秩是指通过一定的近似误差将张量表示为秩为 $r$ 的张量的最小秩。定义为：

rank ~ ( X ) = min ⁡ { r ∣ 对于任意  ϵ > 0 , 存在张量  E , 使得  ∥ E ∥ < ϵ 且 rank ( X + E ) = r } \tilde{\text{rank}}(\mathcal{X}) = \min \left\{ r \mid \text{对于任意 } \epsilon > 0, \text{ 存在张量 } \mathcal{E}, \text{使得 } \|\mathcal{E}\| < \epsilon \text{ 且 } \text{rank}(\mathcal{X} + \mathcal{E}) = r \right\} rank~(X)=min{r∣对于任意 ϵ>0, 存在张量 E,使得 ∥E∥<ϵ 且 rank(X+E)=r}

显然，有 $\widetilde{\text{rank}}(\mathcal{X})\le \text{rank}(\mathcal{X})$。

ALS算法计算CP分解

交替最小二乘法（ALS）是计算CP分解的常用方法。ALS算法通过固定其他矩阵，交替求解每个因子矩阵的最小二乘解。具体算法步骤如下：

$$\mathbf{A}\leftarrow {\mathbf{X}}_{(1)}(\mathbf{C}\odot \mathbf{B}){\left[({\mathbf{C}}^T\mathbf{C})\ast ({\mathbf{B}}^T\mathbf{B})\right]}^{-1}$$

$$\mathbf{B}\leftarrow {\mathbf{X}}_{(2)}(\mathbf{C}\odot \mathbf{A}){\left[({\mathbf{C}}^T\mathbf{C})\ast ({\mathbf{A}}^T\mathbf{A})\right]}^{-1}$$

$$\mathbf{C}\leftarrow {\mathbf{X}}_{(3)}(\mathbf{B}\odot \mathbf{A}){\left[({\mathbf{B}}^T\mathbf{B})\ast ({\mathbf{A}}^T\mathbf{A})\right]}^{-1}$$

该过程不断迭代，直到收敛。

参考

1. https://www.kolda.net/publication/TensorReview.pdf