【张量分解(二)】CP分解

本文是对论文Tensor Decompositions and Applications进行了翻译、整理、筛选和适当的补充，如何希望深入理解可以阅读原文。

【张量分解(一)】符号与基础知识 【张量分解(二)】CP分解 【张量分解(三)】Tucker分解

CP分解就是将一个张量分解成多个单秩张量的和。例如，给定一个三阶张量 X ∈ R I × J × K \mathcal{X}\in\mathbb{R}^{I\times J\times K} X∈RI×J×K，则CP分解可以写为 X ≈ ∑ r = 1 R a r ∘ b r ∘ c r \mathcal{X}\approx\sum_{r=1}^{R}\textbf{a}_r\circ\textbf{b}_r\circ\textbf{c}_r X≈r=1∑R​ar​∘br​∘cr​ 其中， ∘ \circ ∘是指向量外积， R R R是正整数且 a r ∈ R I \textbf{a}_r\in\mathbb{R}^I ar​∈RI, b r ∈ R J \textbf{b}_r\in\mathbb{R}^J br​∈RJ, c r ∈ R K \textbf{c}_r\in\mathbb{R}^K cr​∈RK。下图展示了三阶张量的CP分解 将上面的CP分解展开，也可以写作 x i j k ≈ ∑ r = 1 R a i r b j r c k r , i = 1 , 2 , … , I , j = 1 , 2 , … , J , k = 1 , 2 , … , K x_{ijk}\approx\sum_{r=1}^R a_{ir}b_{jr}c_{kr},\quad i=1,2,\dots,I,j=1,2,\dots,J, k=1,2,\dots,K xijk​≈r=1∑R​air​bjr​ckr​,i=1,2,…,I,j=1,2,…,J,k=1,2,…,K 此外，对于三阶张量来说，可以从通道切片(frontal slice)的角度表示CP分解 X k ≈ A D ( k ) B T ， D ( k ) ≡ d i a g ( c k : ) , k = 1 , … , K \textbf{X}_k\approx\textbf{A}\textbf{D}^{(k)}\textbf{B}^T，\textbf{D}^{(k)}\equiv diag(\textbf{c}_{k:}),k=1,\dots,K Xk​≈AD(k)BT，D(k)≡diag(ck:​),k=1,…,K 其中， X k \textbf{X}_k Xk​表示张量 X \mathcal{X} X的第k个通道切片。对于行切片和列切片也可以写出类似的公式。

在文章【张量分解(一)】符号与基础知识中介绍过张量的矩阵化。这里主要介绍将张量转换为矩阵后的CP分解。 首先，定义因子矩阵(factor matrices)为CP分解中组成单秩张量的同一维度的向量合并成的矩阵(这个表述有点绕)。具体来说，就是把所有的 a \textbf{a} a向量合并成一个矩阵 A = [ a 1 a 2 … a R ] \textbf{A}=[\textbf{a}_1\quad\textbf{a}_2\quad\dots\quad\textbf{a}_R] A=[a1​a2​…aR​]。同理，还可以合成因子矩阵 B \textbf{B} B和 C \textbf{C} C。那么矩阵化后的张量CP分解形式如下： X ( 1 ) ≈ A ( B ⊙ C ) T \textbf{X}_{(1)}\approx\textbf{A}(\textbf{B}\odot\textbf{C})^T X(1)​≈A(B⊙C)T X ( 2 ) ≈ B ( C ⊙ A ) T \textbf{X}_{(2)}\approx\textbf{B}(\textbf{C}\odot\textbf{A})^T X(2)​≈B(C⊙A)T X ( 3 ) ≈ C ( B ⊙ A ) T \textbf{X}_{(3)}\approx\textbf{C}(\textbf{B}\odot\textbf{A})^T X(3)​≈C(B⊙A)T 其中， ⊙ \odot ⊙表示Khatri-Rao积， X ( i ) \textbf{X}_{(i)} X(i)​表示张量 X \mathcal{X} X的模i矩阵化后的矩阵。

为了更加简洁的表达，CP分解可以简写如下 X ≈ ⟮ A , B , C ⟯ \mathcal{X}\approx\lgroup\textbf{A},\textbf{B},\textbf{C}\rgroup X≈⟮A,B,C⟯ 实在是打不出空心方括号(摊手)，只能用 ⟮ ⟯ \lgroup\rgroup ⟮⟯代替了。 通常，假设矩阵 A \textbf{A} A, B \textbf{B} B和 C \textbf{C} C的列向量是标准化后的向量，并且将提取出来的权重合并入向量 λ ∈ R R \mathrm{\lambda}\in\mathbb{R}^R λ∈RR，因此CP分解还可以写成 X ≈ ∑ r = 1 R λ r a r ∘ b r ∘ c r = ⟮ λ ; A , B , C ⟯ \mathcal{X}\approx\sum_{r=1}^{R}\lambda_{r}\textbf{a}_r\circ\textbf{b}_r\circ\textbf{c}_r=\lgroup\mathrm{\lambda};\textbf{A},\textbf{B},\textbf{C}\rgroup X≈r=1∑R​λr​ar​∘br​∘cr​=⟮λ;A,B,C⟯

先前主要介绍的是三阶张量的CP分解，主要是因为其具有广泛的适用性。对于N阶张量 X ∈ R I 1 × I 2 × ⋯ × I N \mathcal{X}\in\mathbb{R}^{I_1\times I_2\times \dots \times I_N} X∈RI1​×I2​×⋯×IN​，其CP分解为 X ≈ ∑ r = 1 R λ r a r ( 1 ) ∘ a r ( 2 ) ∘ ⋯ ∘ a r ( N ) = ⟮ λ ; A ( 1 ) , A ( 2 ) , … , A ( N ) ⟯ \mathcal{X}\approx\sum_{r=1}^{R}\lambda_{r}\textbf{a}_r^{(1)}\circ\textbf{a}_r^{(2)}\circ\dots\circ\textbf{a}_r^{(N)}=\lgroup\mathrm{\lambda};\textbf{A}^{(1)},\textbf{A}^{(2)},\dots,\textbf{A}^{(N)}\rgroup X≈r=1∑R​λr​ar(1)​∘ar(2)​∘⋯∘ar(N)​=⟮λ;A(1),A(2),…,A(N)⟯ 其中， λ ∈ R R \mathrm{\lambda}\in\mathbb{R}^R λ∈RR且 A ( n ) ∈ R I n × R , n = 1 , 2 , … , N \textbf{A}^{(n)}\in\mathbb{R}^{I_n\times R},n=1,2,\dots,N A(n)∈RIn​×R,n=1,2,…,N

类似的，N阶张量 X \mathcal{X} X进行模n矩阵化后的CP分解为 X ( n ) ≈ A ( n ) Λ ( A ( N ) ⊙ ⋯ ⊙ A n + 1 ⊙ A n − 1 ⊙ ⋯ ⊙ A ( 1 ) ) T \textbf{X}_{(n)}\approx\textbf{A}^{(n)}\mathrm{\Lambda}(\textbf{A}^{(N)}\odot\dots\odot\textbf{A}^{n+1}\odot\textbf{A}^{n-1}\odot\dots\odot\textbf{A}^{(1)})^T X(n)​≈A(n)Λ(A(N)⊙⋯⊙An+1⊙An−1⊙⋯⊙A(1))T 其中，对角矩阵 Λ = d i a g ( λ ) \mathrm{\Lambda}=diag(\mathrm{\lambda}) Λ=diag(λ)。

用于生成张量 X \mathcal{X} X所需要的单秩张量的最小数量即为张量 X \mathcal{X} X的秩，用 r a n k ( X ) rank{\mathcal{(X)}} rank(X)表示。换个角度，张量的秩就是CP分解时单秩张量数量的最小值。

此外，张量的秩与矩阵秩的定义非常相似，但是二值的性质非常的不同。例如，实数张量的秩在实数域 R \mathbb{R} R和复数域 C \mathbb{C} C上可能会不同。另一个张量秩和矩阵秩的显著不同是，当前没有一个直接的方法来确定给定张量的秩。例如，Krushkal对特定的 9 × 9 × 9 9\times9\times9 9×9×9的张量进行分析，只能确定其秩在18到23之间。在实际应用中，张量的秩是通过CP分解来确定的。

最大秩：一类张量能够达到的最大的秩称为张量的最大秩(maximum rank)。典型秩：一个从均匀连续分别中随机抽取元素所组成的张量中，出现概率大于0的任何秩。 具体来说，对于所有形状为 I × J I\times J I×J的矩阵，最大秩和典型秩均等于 m i n { I , J } min\{I,J\} min{I,J}。但是对于张量来说，最大秩和典型秩可能不相同，而且典型秩可能不只一个。例如 2 × 2 × 2 2\times 2\times 2 2×2×2张量的典型秩为2或3，通过蒙特卡洛实验也可以发现秩为2的张量占79%，秩为3的张量占21%，秩为1的张量在理论上虽然可能，但是实际概率为0。 对于一般的三阶张量 X ∈ R I × J × K \mathcal{X}\in\mathbb{R}^{I\times J\times K} X∈RI×J×K，当前只知道其最大秩的一个弱上界 r a n k ( X ) ≤ m i n { I J , I K , J K } rank(\mathcal{X})\leq min\{IJ,IK,JK\} rank(X)≤min{IJ,IK,JK} 对于特定形状或类型的张量来说，有可能存在一些确定最大秩和典型秩的具体值或者范围的方法，可以参考原文Tensor Decompositions and Applications

高阶张量的一个有趣的特性是它的秩分解是唯一的，而通常矩阵分解不是。

对于秩为 R R R的矩阵 X ∈ R I × J \textbf{X}\in\mathbb{R}^{I\times J} X∈RI×J，其秩分解可以写为 X = AB T = ∑ r = 1 R a r ∘ b r \textbf{X}=\textbf{AB}^T=\sum_{r=1}^R\textbf{a}_r\circ\textbf{b}_r X=ABT=r=1∑R​ar​∘br​ 具体来说，对于矩阵 X \textbf{X} X的SVD分解为 U Σ V T \mathrm{U\Sigma V}^T UΣVT，为了与上面的秩分解对于，令 A = U Σ \textbf{A}=\mathrm{U\Sigma} A=UΣ且 B = V \textbf{B}=\mathrm{V} B=V。但是，如果令 A = U Σ W \textbf{A}=\mathrm{U\Sigma W} A=UΣW且 B = V W \textbf{B}=\mathrm{VW} B=VW,其中 W \mathrm{W} W是 R × R R\times R R×R的正交矩阵( W T W = E W^TW=E WTW=E)，同样也满足矩阵秩分解的定义。 换句话说，我们可以轻易的构造两个完全不同的单秩矩阵集合，但是集合中的矩阵相加就等于原始矩阵。而SVD分解的唯一性仅仅是因为正交约束的加入。

通常，在十分微弱的约束条件下，张量的CP分解就是唯一的。对于秩为 R R R的三阶张量 X ∈ R I × J × K \mathcal{X}\in\mathbb{R}^{I\times J\times K} X∈RI×J×K，其CP分解为 X = ∑ r = 1 R a r ∘ b r ∘ c r = ⟮ A , B , C ⟯ \mathcal{X}=\sum_{r=1}^{R}\textbf{a}_r\circ\textbf{b}_r\circ\textbf{c}_r=\lgroup\textbf{A},\textbf{B},\textbf{C}\rgroup X=r=1∑R​ar​∘br​∘cr​=⟮A,B,C⟯ 而唯一性就是指上面的分解中是唯一可能的单秩矩阵的组合。当然，这是排除了缩放和重新排列后的唯一性。例如这里使用置换矩阵对分解后的单秩矩阵的列进行重排列 X = ⟮ A , B , C ⟯ = ⟮ A Π , B Π , C Π ⟯ \mathcal{X}=\lgroup\textbf{A},\textbf{B},\textbf{C}\rgroup=\lgroup\textbf{A}\Pi,\textbf{B}\Pi,\textbf{C}\Pi\rgroup X=⟮A,B,C⟯=⟮AΠ,BΠ,CΠ⟯ 其中， Π \Pi Π是 R × R R\times R R×R的置换矩阵。同样，对于将CP分解中的向量进行缩放也不影响CP分解的结果，例如 X = ∑ r = 1 R ( α r a r ) ∘ ( β r b r ) ∘ ( γ r c r ) \mathcal{X}=\sum_{r=1}^R(\alpha_r\textbf{a}_r)\circ(\beta_r\textbf{b}_r)\circ(\gamma_r\textbf{c}_r) X=r=1∑R​(αr​ar​)∘(βr​br​)∘(γr​cr​) 其中， α r β r γ r = 1 , r = 1 , . . . , R \alpha_r\beta_r\gamma_r=1,r=1,...,R αr​βr​γr​=1,r=1,...,R

对于CP分解 X = ⟮ A , B , C ⟯ \mathcal{X}=\lgroup\textbf{A},\textbf{B},\textbf{C}\rgroup X=⟮A,B,C⟯，令 k A k_A kA​、 k B k_B kB​、 k C k_C kC​分别表示矩阵 A \textbf{A} A、 B \textbf{B} B、 C \textbf{C} C的秩，那么CP分解唯一的充分条件是 k A + k B + k C ≥ 2 R + 2 k_A+k_B+k_C\ge2R+2 kA​+kB​+kC​≥2R+2 将上面的条件扩展至N维，对于张量 X = ∑ r = 1 R a r ( 1 ) ∘ a r ( 2 ) ∘ ⋯ ∘ a r ( N ) = ⟮ A ( 1 ) , A ( 2 ) , … , A ( N ) ⟯ \mathcal{X}=\sum_{r=1}^R\textbf{a}_{r}^{(1)}\circ \textbf{a}_{r}^{(2)}\circ\dots\circ\textbf{a}_{r}^{(N)}=\lgroup\textbf{A}^{(1)},\textbf{A}^{(2)},\dots,\textbf{A}^{(N)}\rgroup X=r=1∑R​ar(1)​∘ar(2)​∘⋯∘ar(N)​=⟮A(1),A(2),…,A(N)⟯，其CP分解唯一性的充分条件为 ∑ n = 1 N k A ( n ) ≥ 2 R + ( N − 1 ) \sum_{n=1}^N k_{\textbf{A}^{(n)}}\ge2R+(N-1) n=1∑N​kA(n)​≥2R+(N−1)

上面的充分条件在 R = 2 R=2 R=2或 R = 3 R=3 R=3的条件下，也是CP分解唯一性的必要条件，但是当 R > 3 R>3 R>3则不成立。更加广泛的CP分解唯一性的必要条件为 m i n { r a n k ( A ⊙ B ) , r a n k ( A ⊙ C ) , r a n k ( B ⊙ C ) } = R min\{rank(\textbf{A}\odot\textbf{B}),rank(\textbf{A}\odot\textbf{C}),rank(\textbf{B}\odot\textbf{C})\}=R min{rank(A⊙B),rank(A⊙C),rank(B⊙C)}=R 推广的N维情况下，则 m i n n = 1 , … , N r a n k ( A ( 1 ) ⊙ ⋯ ⊙ A ( n − 1 ) ⊙ A ( n + 1 ) ⊙ ⋯ ⊙ A ( N ) ) = R min_{n=1,\dots,N}rank(\textbf{A}^{(1)}\odot\dots\odot\textbf{A}^{(n-1)}\odot\textbf{A}^{(n+1)}\odot\dots\odot\textbf{A}^{(N)})=R minn=1,…,N​rank(A(1)⊙⋯⊙A(n−1)⊙A(n+1)⊙⋯⊙A(N))=R 但是，由于性质 r a n k ( A ⊙ B ) ≤ r a n k ( A ⊗ B ) ≤ r a n k ( A ) ⋅ r a n k ( B ) rank(\textbf{A}\odot\textbf{B})\le rank(\textbf{A}\otimes\textbf{B})\le rank(\textbf{A})\cdot rank(\textbf{B}) rank(A⊙B)≤rank(A⊗B)≤rank(A)⋅rank(B) 因此，N维下的必要条件可以扩展为 m i n n = 1 , … , N ( r a n k ( A ( 1 ) ) ⋅ ⋯ ⋅ r a n k ( A ( n − 1 ) ) ⋅ r a n k ( A ( n + 1 ) ) ⋅ ⋯ ⋅ r a n k ( A ( N ) ) ) ≥ R min_{n=1,\dots,N}\Big(rank(\textbf{A}^{(1)})\cdot\dots\cdot rank(\textbf{A}^{(n-1)})\cdot rank(\textbf{A}^{(n+1)})\cdot\dots\cdot rank(\textbf{A}^{(N)})\Big)\ge R minn=1,…,N​(rank(A(1))⋅⋯⋅rank(A(n−1))⋅rank(A(n+1))⋅⋯⋅rank(A(N)))≥R

对于秩为 R R R的三阶张量 X ∈ R I × J × K \mathcal{X}\in\mathbb{R}^{I\times J\times K} X∈RI×J×K，当满足条件 R ≤ K 并 且 R ( R − 1 ) ≤ I ( I − 1 ) J ( J − 1 ) / 2 R\le K并且R(R-1)\le I(I-1)J(J-1)/2 R≤K并且R(R−1)≤I(I−1)J(J−1)/2 则，其CP分解是唯一的。 类似的，对于秩为R的四阶张量 X ∈ R I × J × K × L \mathcal{X}\in\mathbb{R}^{I\times J\times K\times L} X∈RI×J×K×L，其CP分解唯一的条件是 R ≤ L 并 且 R ( R − 1 ) ≤ I J K ( 3 I J K − I J − I K − J K − I − J − K + 3 ) / 4 R\le L并且R(R-1)\le IJK(3IJK-IJ-IK-JK-I-J-K+3)/4 R≤L并且R(R−1)≤IJK(3IJK−IJ−IK−JK−I−J−K+3)/4

给定一个秩为 R R R的矩阵 A \textbf{A} A，那么该矩阵的SVD分解可以写作： A = ∑ r = 1 R σ r u r ∘ v r ， 其 中 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ R \textbf{A}=\sum_{r=1}^R\sigma_r\textbf{u}_r\circ\textbf{v}_r，其中\sigma_1\ge\sigma_2\ge\dots\ge\sigma_R A=r=1∑R​σr​ur​∘vr​，其中σ1​≥σ2​≥⋯≥σR​ 那么该矩阵的秩k近似，可以直接使用SVD分解中前k个部分，即 B = ∑ r = 1 k σ r u r ∘ v r \textbf{B}=\sum_{r=1}^k\sigma_r\textbf{u}_r\circ\textbf{v}_r B=r=1∑k​σr​ur​∘vr​

上面对于矩阵的结果并不适用于张量。给定一个秩为 R R R的三阶张量，其CP分解为 X = ∑ r = 1 R λ r a r ∘ b r ∘ c r \mathcal{X}=\sum_{r=1}^R\lambda_r\textbf{a}_r\circ\textbf{b}_r\circ\textbf{c}_r X=r=1∑R​λr​ar​∘br​∘cr​ 按上面矩阵的低秩近似来看，三阶张量的秩k近似也应该是其中k个部分的和，但实际情况并非如此。 Kolda提供过一个例子，对于一个三阶张量的单秩近似并不是秩2近似的组成部分(在矩阵的低秩分解中一定成立)。因此会得出一个推论，一个张量的最优秩k近似中的k个组成部分并不是按顺序求得的，而是需要同时被发现的。 总的来说，这个问题比较复杂，有时一个张量的最优秩k近似不一定存在。如果一个张量可以通过低秩的因式分解任意逼近，那么该张量就是一个退化张量。 举一个具体的例子来说，给定一个秩为3的具体三阶张量 X ∈ R I × J × K \mathcal{X}\in\mathbb{R}^{I\times J\times K} X∈RI×J×K为 X = a 1 ∘ b 1 ∘ c 2 + a 1 ∘ b 2 ∘ c 1 + a 2 ∘ b 1 ∘ c 1 \mathcal{X}=\textbf{a}_1\circ\textbf{b}_1\circ\textbf{c}_2+\textbf{a}_1\circ\textbf{b}_2\circ\textbf{c}_1+\textbf{a}_2\circ\textbf{b}_1\circ\textbf{c}_1 X=a1​∘b1​∘c2​+a1​∘b2​∘c1​+a2​∘b1​∘c1​ 其中, A ∈ R I × 2 , B ∈ R J × 2 , C ∈ R K × 2 \textbf{A}\in\mathbb{R}^{I\times 2},\textbf{B}\in\mathbb{R}^{J\times 2},\textbf{C}\in\mathbb{R}^{K\times 2} A∈RI×2,B∈RJ×2,C∈RK×2是由于上式中对应的向量组成的，且这三个矩阵的列向量线性无关。 上面描述的张量可以使用下面的下面的秩2张量进行任意的近似 Y = n ( a 1 + 1 n a 2 ) ∘ ( b 1 + 1 n b 2 ) ∘ ( c 1 + 1 n c 2 ) − n a 1 ∘ b 1 ∘ c 1 \mathcal{Y}=n\Big(\textbf{a}_1+\frac{1}{n}\textbf{a}_2\Big)\circ\Big(\textbf{b}_1+\frac{1}{n}\textbf{b}_2\Big)\circ\Big(\textbf{c}_1+\frac{1}{n}\textbf{c}_2\Big)-n\textbf{a}_1\circ\textbf{b}_1\circ\textbf{c}_1 Y=n(a1​+n1​a2​)∘(b1​+n1​b2​)∘(c1​+n1​c2​)−na1​∘b1​∘c1​ 原始的秩3张量 X \mathcal{X} X和近似的秩2张量 Y \mathcal{Y} Y之间的误差为 ∥ X − Y ∥ = 1 n ∥ a 2 ∘ b 2 ∘ c 1 + a 2 ∘ b 1 ∘ c 2 + a 1 ∘ b 2 ∘ c 2 + 1 n a 2 ∘ b 2 ∘ c 2 ∥ \Vert\mathcal{X}-\mathcal{Y}\Vert=\frac{1}{n}\Big\Vert\textbf{a}_2\circ\textbf{b}_2\circ\textbf{c}_1+\textbf{a}_2\circ\textbf{b}_1\circ\textbf{c}_2+\textbf{a}_1\circ\textbf{b}_2\circ\textbf{c}_2+\frac{1}{n}\textbf{a}_2\circ\textbf{b}_2\circ\textbf{c}_2\Big\Vert ∥X−Y∥=n1​∥∥∥​a2​∘b2​∘c1​+a2​∘b1​∘c2​+a1​∘b2​∘c2​+n1​a2​∘b2​∘c2​∥∥∥​ 当然，这个误差可以任意的小。

在不存在最优低秩近似的情况下，可以考虑边界秩。其定义为，能够以任意非零误差充分近似给定张量的最小单秩张量的数量。形式化的定义为 r a n k ~ ( X ) = m i n { r ∣ 对 于 任 意 ϵ > 0 , 均 存 在 一 个 张 量 E 满 足 ∥ E ∥ < ϵ 且 r a n k ( X + E ) = r } \widetilde{rank}(\mathcal{X})=min\{r|对于任意\epsilon>0,均存在一个张量\mathcal{E}满足\Vert\mathcal{E}\Vert