ABSTRACT

Sparsity in tensor decomposition has solved some difficulties encountered in actual application. This paper simply introduces related concepts of tensor and CP (CANDECOMP/PARAFAC) decomposition. Then, we propose the decomposition based on Lq norm ( $0<q<1$ ), and solve it by Alternating Direction of Method of Multipliers. This paper also gives an explicit solution when $q=\frac{1}{2}$.

Keywords:Sparsity, Tensor Decomposition, Alternating Direction of Method of Multipliers

基于Lq范数的稀疏张量分解问题

姜玉

广西大学数学与信息科学学院，广西 南宁

收稿日期：2020年2月25日；录用日期：2020年3月9日；发布日期：2020年3月16日

摘 要

在张量分解中，稀疏性的引入解决了实际应用中遇到的一些困难，本文简单的介绍了张量及张量CP分解的相关概念，在已有研究的基础上提出基于Lq范数( $0<q<1$ )的稀疏张量分解问题，并使用乘子交替方向法来进行求解，以及给出 $q=\frac{1}{2}$ 时问题解的形式。

关键词 :稀疏性，张量分解，乘子交替方向法

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

张量分解可以应用于多维数据的数据压缩、可视化、探索，这使得它在神经成像、人脸识别、核磁共振成像等领域有着重要的作用。而实际应用的过程中也会遇到一些困难，如大量的数据需要占据较大的内存空间，计算复杂度较高。为了解决这样的问题，学者们提出将稀疏性引入到张量分解的问题中。

在文献 [1] 中，作者给出了稀疏性可取的原因：第一，稀疏性进一步压缩了多维数据集使得减轻了存储压力；第二，因为许多特征并不活跃，稀疏性的引入为高维张量的特征选取提供了一种自动的工具；第三，在高维张量下，数据的可视化和解释较为困难，而稀疏性限制了特征的数量从而简化了数据分析结果的可视化和解释。

稀疏性不仅具有良好的理论性质，而且在文献 [1] [2] [3] [4] 中通过数值结果表明在稀疏情况下考虑的张量分解有很好的数值性能。

1.1. 张量的符号和运算

为了讨论张量分解以及进一步地去讨论带有稀疏性的张量分解，我们需要简单地了解张量的符号及相关运算，文献 [5] [6] 给出了这些内容。张量作为向量和矩阵在高维空间的推广，可以容纳较大的多维数据。若张量为一阶，我们可以将其看做为向量，二阶的张量则为矩阵。三阶及三阶以上的张量成为高阶张量，我们所讨论的张量常指高阶张量。

张量常用 $\mathcal{A},\mathcal{B},\mathcal{C},\cdots$ 表示，矩阵用大写字母 $A,B,C,\cdots$ 表示，向量用 $a,b,c,\cdots$ 表示。N阶张量可以记为 $\mathcal{A}\in {ℝ}^{I_1\times I_2\times \cdots \times I_N}$，$I_i$ 是它的第i个模数， $i=1,2,\cdots ,N$。它的元素表示为 ${\mathcal{A}}_{i_1{i}_2\cdots i_N}$，其中 $i_k=1,2,\cdots ,I_k;k=1,2,\cdots ,N$。

张量可以表为若干个向量的外积，即 $\mathcal{A}=u^{\left(1\right)}\circ u^{\left(2\right)}\circ \cdots \circ u^{\left(N\right)}$。此时，张量 $\mathcal{A}$ 为秩为1的张量。

张量的Frobenius范数定义为 ${\Vert \mathcal{A}\Vert }_F=\langle \mathcal{A},\mathcal{A}\rangle ={\left({\displaystyle {\sum }_{i_1,\cdots ,i_N}{\mathcal{A}}_{i_1\cdots i_N}^2}\right)}^{\frac{1}{2}}$。

1.2. 张量的CP分解

CP分解是张量最为常见的分解方法之一，它将张量表为一系列秩为1的张量的和。对N阶张量 $\mathcal{A}\in {ℝ}^{I_1\times I_2\times \cdots \times I_N}$，它的CP分解可以写为

$\mathcal{A}={\displaystyle {\sum }_{i=1}^r{u}_i^{\left(1\right)}\circ u_i^{\left(2\right)}\circ \cdots \circ u_i^{\left(N\right)}},$

其中 $r=\min \left\{R|\mathcal{A}={\displaystyle {\sum }_{i=1}^R{u}_i^{\left(1\right)}\circ u_i^{\left(2\right)}\circ \cdots \circ u_i^{\left(N\right)}}\right\}$ 是张量的秩。张量的CP分解保证了张量分解的唯一性。

一般将张量分解的问题转化为优化问题，于是N阶张量的CP分解问题等价于优化问题：

$\min \frac{1}{2}{\Vert \mathcal{A}-{\displaystyle {\sum }_{i=1}^r{u}_i^{\left(1\right)}\circ u_i^{\left(2\right)}\circ \cdots \circ u_i^{\left(N\right)}}\Vert }_{\text{F}}^2.$ (1)

令

$U^{\left(1\right)}=\left(u_1^{\left(1\right)},u_2^{\left(1\right)},\cdots ,u_r^{(1)}\right)$

$U^{\left(2\right)}=\left(u_1^{\left(2\right)},u_2^{\left(2\right)},\cdots ,u_r^{(2)}\right)$

$\cdots$

$U^{\left(N\right)}=\left(u_1^{\left(N\right)},u_2^{\left(N\right)},\cdots ,u_r^{(N)}\right)$

则优化问题(1)又可以写成

$\min \frac{1}{2}{\Vert \mathcal{A}-〚U^{\left(1\right)},U^{\left(2\right)},\cdots ,U^{\left(N\right)}〛\Vert }_F^2,$ (2)

其中 $〚U^{\left(1\right)},U^{\left(2\right)},\cdots ,U^{\left(N\right)}〛={\displaystyle {\sum }_{i=1}^r{u}_i^{\left(1\right)}\circ u_i^{\left(2\right)}\circ \cdots \circ u_i^{\left(N\right)}}$。 $U^{\left(1\right)},U^{\left(2\right)},\cdots ,U^{\left(N\right)}$ 称为张量 $\mathcal{A}$ 的因子矩阵，也是我们在张量分解问题中要求得的解。

2. 具有稀疏性的张量分解问题

因目标张量数据过大，我们需要注意到在实际处理中遇到的问题。稀疏性的引入，可以帮我们解决如占据内存过大、不相关不活跃的数据过多而很难从中找出我们所需的特征等类似的问题。

为引入稀疏性，研究者们考虑在张量分解的优化问题中加入因子的正则范数。在已有的文献中，我们可以找到关于在优化问题中加入因子矩阵的L1范数的讨论。于是，稀疏的张量CP分解问题可以等价于

$\min \frac{1}{2}{\Vert \mathcal{A}-〚U^{\left(1\right)},U^{\left(2\right)},\cdots ,U^{\left(N\right)}〛\Vert }_F^2+{\displaystyle {\sum }_{i=1}^N{\lambda }_i{\Vert U^{\left(i\right)}\Vert }_1},$

其中 $\mathcal{A}\in {ℝ}^{I_1\times I_2\times \cdots \times I_N}$，$U^{\left(i\right)}\in {ℝ}^{I_i\times r},i=1,2,\cdots ,N$。

为计算方便，我们常以三阶张量为例，更高阶的情况同三阶张量的求解思路及方法一致。

对三阶的张量 $\mathcal{A}\in {ℝ}^{m\times p\times q}$，加入因子的L1范数，它的稀疏分解问题为

$\min \frac{1}{2}{\Vert \mathcal{A}-{\displaystyle {\sum }_{i=1}^r{x}_i\circ y_i\circ z_i}\Vert }_F^2+{\lambda }_1{\Vert X\Vert }_1+{\lambda }_2{\Vert Y\Vert }_1+{\lambda }_3{\Vert Z\Vert }_1,$

其中 $X=\left(x_1,x_2,\cdots ,x_r\right),Y=\left(y_1,y_2,\cdots ,y_r\right),Z=\left(z_1,z_2,\cdots ,z_r\right)$ 分别为 $m\times r,p\times r,q\times r$ 的矩阵。

在统计学和机器学习中，Lq范数( $0<q<1$ )中的q的取值越小，求得的解的稀疏性越好。我们用Lq范数来代替L1范数，于是得到本文所提出的基于Lq范数的稀疏张量分解。它的优化问题为

$\min \frac{1}{2}{\Vert \mathcal{A}-{\displaystyle {\sum }_{i=1}^r{x}_i\circ y_i\circ z_i}\Vert }_F^2+{\lambda }_1{\Vert X\Vert }_q+{\lambda }_2{\Vert Y\Vert }_q+{\lambda }_3{\Vert Z\Vert }_q,$

等价地，也可以为

$\min \frac{1}{2}{\Vert \mathcal{A}-〚X,Y,Z〛\Vert }_F^2+{\lambda }_1{\Vert X\Vert }_q+{\lambda }_2{\Vert Y\Vert }_q+{\lambda }_3{\Vert Z\Vert }_q.$ (3)

3. 使用乘子交替方向法求解目标优化问题

这一节中，我们首先对乘子交替方向法进行简单的描述，随后给出问题(3)在使用乘子交替方向法的求解思路及 $q=\frac{1}{2}$ 时问题解的形式。

3.1. 乘子交替方向法

乘子交替方向法是一种求解优化问题的计算框架，它适用于求解大规模分布式优化问题。通过分解协调过程，将问题分解为多个局部小问题，求解出局部小问题的解从而得到原问题的解。

考虑优化问题

$\min f\left(x\right)+g(y)$

$\text{s}\text{.t}\text{.}x-y=0;$

该问题的迭代求解算法为

$x^{k+1}\in \arg \min L_{\beta }\left(x,y^k,{\lambda }^k\right),$

$y^{k+1}\in \arg \min L_{\beta }\left(x^{k+1},y,{\lambda }^k\right),$

${\lambda }^{k+1}={\lambda }^k-\beta \left(x^{k+1}-y^{k+1}\right),$

增广拉格朗日函数为 $L_{\beta }\left(x,y,\lambda \right)=f\left(x\right)+g\left(y\right)-{\lambda }^{\text{T}}\left(x-y\right)+\frac{\beta }{2}{\Vert x-y\Vert }^2$，$\beta >0$ 是罚参数， $\lambda$ 是拉格朗日乘子。

3.2. 求解目标问题

我们加入约束条件 $X=L,Y=M,Z=N$，问题(3)变为

$\min \frac{1}{2}{\Vert \mathcal{A}-〚X,Y,Z〛\Vert }_F^2+{\lambda }_1{\Vert L\Vert }_q+{\lambda }_2{\Vert M\Vert }_q+{\lambda }_3{\Vert N\Vert }_q,$

$\text{s}\text{.t}\text{.}X=L,Y=M,Z=N,$

它的增广拉格朗日函数

$\begin{array}{l}L\left(X,Y,Z,L,M,N,{\Lambda }_1,{\Lambda }_2,{\Lambda }_3\right),\\ =\frac{1}{2}{\Vert \mathcal{A}-〚X,Y,Z〛\Vert }_F^2+{\lambda }_1{\Vert L\Vert }_q+{\lambda }_2{\Vert M\Vert }_q+{\lambda }_3{\Vert N\Vert }_q-\langle {\Lambda }_1,X-L\rangle \\ -\langle {\Lambda }_2,Y-M\rangle -\langle {\Lambda }_3,Z-N\rangle +\frac{{\tau }_1}{2}{\Vert X-L\Vert }_F^2+\frac{{\tau }_2}{2}{\Vert Y-M\Vert }_F^2+\frac{{\tau }_3}{2}{\Vert Z-N\Vert }_F^2\end{array}$

它的迭代算法为

$L^{k+1}=\arg \min \frac{{\tau }_1}{2}{\Vert L-X^k-\frac{1}{{\tau }_1}{\Lambda }_1^k\Vert }_F^2+{\lambda }_1{\Vert L\Vert }_q,$

$X^{k+1}=\arg \min \frac{1}{2}{\Vert \mathcal{A}-{\displaystyle {\sum }_{i=1}^r{x}_i\circ y_i^k\circ z_i^k}\Vert }_F^2+\frac{{\tau }_1}{2}{\Vert L^{k+1}-X-\frac{1}{{\tau }_1}{\Lambda }_1^k\Vert }_F^2,$

$M^{k+1}=\arg \min \frac{{\tau }_2}{2}{\Vert M-Y^k-\frac{1}{{\tau }_2}{\Lambda }_2^k\Vert }_F^2+{\lambda }_2{\Vert M\Vert }_q,$

$Y^{k+1}=\arg \min \frac{1}{2}{\Vert \mathcal{A}-{\displaystyle {\sum }_{i=1}^r{x}_i^{k+1}\circ y_i\circ z_i^k}\Vert }_F^2+\frac{{\tau }_2}{2}{\Vert M^{k+1}-Y-\frac{1}{{\tau }_2}{\Lambda }_2^k\Vert }_F^2,$

$N^{k+1}=\arg \min \frac{{\tau }_3}{2}{\Vert N-Z^k-\frac{1}{{\tau }_3}{\Lambda }_3^k\Vert }_F^2+{\lambda }_3{\Vert N\Vert }_q,$

$Z^{k+1}=\arg \min \frac{1}{2}{\Vert \mathcal{A}-{\displaystyle {\sum }_{i=1}^r{x}_i^{k+1}\circ y_i^{k+1}\circ z_i}\Vert }_F^2+\frac{{\tau }_{\text{3}}}{2}{\Vert N^{k+1}-Z-\frac{1}{{\tau }_3}{\Lambda }_3^k\Vert }_F^2,$

${\Lambda }_1^{k+1}={\Lambda }_1^k-{\lambda }_1\left(L^{k+1}-X^{k+1}\right),$

${\Lambda }_2^{k+1}={\Lambda }_2^k-{\lambda }_2\left(M^{k+1}-Y^{k+1}\right),$

${\Lambda }_3^{k+1}={\Lambda }_3^k-{\lambda }_3\left(N^{k+1}-Z^{k+1}\right);$

方法的思路是对 $L,X,M,Y,N,Z,{\Lambda }_1,{\Lambda }_2,{\Lambda }_3$ 依次进行迭代，直至问题收敛。求得的矩阵 $X,Y,Z$ 为张量的因子矩阵。

当 $q=\frac{1}{2}$ 时， $L,M,N$ 的子优化问题具有显示解。于是，令，L的优化问题变为

$L^{k+1}=\arg \min \frac{{\tau }_1}{2}{\Vert L-X^k-\frac{1}{{\tau }_1}{\Lambda }_1^k\Vert }_F^2+{\lambda }_1{\Vert L\Vert }_{\frac{1}{2}}$

根据文献 [7] 中的证明，推出相应的阈值算子为

$H_{\frac{2{\lambda }_1}{{\tau }_1}}\left(x\right)=\{\begin{array}{l}\frac{2}{3}x\left(1+\cos \left(\frac{2\pi }{3}-\frac{2\phi \left(x\right)}{3}\right)\right),\left|x\right|>\frac{\sqrt[3]{54}}{4}{\left(\frac{2{\lambda }_1}{{\tau }_1}\right)}^{\frac{2}{3}}\\ 0,其他\end{array}$

其中 $\phi \left(x\right)=\arccos \left(\frac{{\lambda }_1}{4{\tau }_1}{\left(\frac{\left|x\right|}{3}\right)}^{-\frac{3}{2}}\right)$，x对应矩阵 $X^k+\frac{1}{{\tau }_1}{\Lambda }_1^k$ 的每一个元素。M和N的子问题的解可以参照L得出。

X的子优化问题

$X^{k+1}=\arg \min {\Vert \frac{1}{2}\mathcal{A}-{\displaystyle {\sum }_{i=1}^r{x}_i\circ y_i^k\circ z_i^k}\Vert }_F^2+\frac{{\tau }_1}{2}{\Vert L^{k+1}-X-\frac{1}{{\tau }_1}{\Lambda }_1^k\Vert }_F^2$ (4)

的求解涉及到了张量的计算，为降低计算困难，我们可以将张量展开成矩阵的形式。张量的展开是将张量沿某一个模的展开，张量展开成的矩阵包括张量中的每一个元素，且张量沿不同的模展开得到的矩阵也不一定相同。张量按它的第一个模展开所得的矩阵记为 $A_{\left(1\right)}$，它是一个 $m\times pq$ 的矩阵，我们在X的优化问题中选用张量沿第一个模展开的矩阵来计算。问题(4)转化为

$X^{k+1}=\arg \min \frac{1}{2}{\Vert A_{\left(1\right)}-X{\left(Z^k\odot Y^k\right)}^{\text{T}}\Vert }_F^2+\frac{{\tau }_1}{2}{\Vert L^{k+1}-X-\frac{1}{{\tau }_1}{\Lambda }_1^k\Vert }_F^2,$ (5)

$\odot$ 表示矩阵的Khatri-Rao积，等式(5)的右边为最小二乘问题。对(5)求导，

$0={\left(Z^k\odot Y^k\right)}^{\text{T}}\left(A_{\left(1\right)}^{\text{T}}-\left(Z^k\odot Y^k\right)X^{\text{T}}\right)-{\tau }_1\left(L^{k+1}{}^{{}^{\text{T}}}-X^{\text{T}}\right)-{\Lambda }_1^k{}^{{}^{\text{T}}},$

整理后得第k + 1步矩阵X的解

$X^{\text{T}}={\left({\left(Z^k\odot Y^k\right)}^{\text{T}}\left(Z^k\odot Y^k\right)-{\tau }_{1}I\right)}^{-1}\left({\left(Z^k\odot Y^k\right)}^{\text{T}}{A}_{\left(1\right)}^{\text{T}}-{\tau }_1{L}^{k+1}{}^{{}^{\text{T}}}-{\Lambda }_1^k{}^{{}^{\text{T}}}\right).$

$Y,Z$ 的优化问题的求解过程类似，不同的是， $Y,Z$ 的求解所用的展开矩阵分别为沿张量的第二个模和第三个模展开的矩阵。

4. 总结

具有稀疏性的张量分解因其理论性质及在应用中良好的体现，逐渐得到学者们的关注。加入因子L1范数来引入稀疏性在一些文献中得到了验证，而Lq范数( $0<q<\text{1}$ )的情况目前还未有学者提出。本文提出了基于Lq范数的稀疏张量分解问题，同时给出了使用乘子交替方向法求解张量分解问题的思路和过程

以及 $q=\frac{1}{2}$ 时问题所具有的显式解的形式。在接下来的研究中，我们希望能够进行数据实验，和普通的张

量分解以及引入L1范数的稀疏张量分解的结果进行比较，证明基于Lq范数的分解问题的稀疏性以及它具有更好的稀疏性。

文章引用

姜 玉. 基于Lq范数的稀疏张量分解问题
Sparse Tensor Decomposition Based on Lq Norm[J]. 应用数学进展, 2020, 09(03): 301-306. https://doi.org/10.12677/AAM.2020.93036

参考文献