基于截断核范数张量鲁棒主成分分析
Tensor Robust Principal Component Analysis Based on Truncated Nuclear Norm
DOI: 10.12677/AIRR.2020.92008, PDF, HTML, XML, 下载: 616  浏览: 1,406  科研立项经费支持
作者: 杨枥皓:西南大学数学与统计学院,重庆
关键词: 张量分解主成分分析截断核范数图像去噪Tensor Decomposition Principal Component Analysis Truncated Nuclear Norm Image Denoising
摘要: 低管秩张量的分解由于其在图像处理中的实际应用已经在各个领域引起了关注。但是传统的张量分解算法为了得到给定张量的低秩和稀疏成分,利用了全部的数据。尽管这些现存的方法都有较快的收敛速度,但是这些方法都忽略了小奇异值几乎不含信息这一事实。基于这一事实,我们提出了一种新的分解方法。我们的方法通过限制核范数的大小从而简化张量分解。和其他张量恢复方法相较而言,我们提出的方法能在实验中能取得更好的效果。
Abstract: Low-tubal-rank tensor decomposition has been attracting attention of various fields due to the real application in image processing. However, conventional algorithms for tensor decomposition utilise the entire data to obtain the Low-tubal-rank and sparse components of a given tensor. Although many existing methods have fast convergence rates, these methods ignore the fact that small singular values contain little information. Based on this fact, we come up with a new decomposition method. Our method can simplify the tensor decomposition according to constrain the nuclear norm. Compared with the experimental results of many other tensor recovery methods, our proposed method can obtain a better effect.
文章引用:杨枥皓. 基于截断核范数张量鲁棒主成分分析[J]. 人工智能与机器人研究, 2020, 9(2): 64-73. https://doi.org/10.12677/AIRR.2020.92008

1. 引言

随着时代的发展和大数据时代的来临,从高维数据中发现和挖掘低维结构的思想已经在图像分析,视频降噪,模式识别,基因数据分析 [1] [2] [3] [4] 等方面起着越来越重要的作用。一般来讲,假设我们给定一个被观测到的数据矩阵,该矩阵是由另一个低秩矩阵的其中一些元素被噪声污染后得到的。为了从观测矩阵中恢复出,我们希望可以被分解为,其中是低秩矩阵,而中由于只有很少一部分元素才是非零的,所以我们称为稀疏矩阵(这些非零元素即为异常值)。为了解决这个问题,文献 [5] 提出了用鲁棒主成分分析(Robust Principal Component Analysis, RPCA)方法来从被污染的矩阵中恢复出

(1)

RPCA在多项式时间内仍然保持良好的恢复效果和稳定性,所以该方法被广泛地应用于数据分析工作中。遗憾的是,在大部分情况下RPCA只能处理矩阵数据,即二维数组。然而高维数据(即张量)在实际生活和科研工作中随处可见,比如彩色图片,高光谱图像大部分都被编译为三阶张量:行,列元素的分布以及每一个像素的颜色;彩色视频也可以视为四阶张量。张量在图像去噪 [6],视频存储 [7],数据挖掘 [8],背景提取 [9] 中都有着非常广泛的应用。而对于张量形式的分解,具体来说,就是给定一个三阶张量,它可以被分解和被表示为,其中的空间内分别具有低秩和稀疏的结构。

值得注意的是,关于张量秩的定义并不是唯一的,其中使用比较广泛的两种张量秩是由CANDECOMP/PARAFAC (CP) [10] 分解和Tucker [11] 分解得到的CP秩和Tucker秩。但上述两种秩的定义都有其局限性:文献 [12] 已经证明正确地估计CP秩是一个NP-hard的问题,而Tucker秩是一个向量而非标量,不适合用于比较大小。在本文中,我们采取基于张量SVD分解的管秩(tensor tubal rank,见定义7)作为张量秩的定义。因此张量形式下低秩和稀疏部分可以通过下面的张量鲁棒主成分分析(Tensor Robust Principal Component analysis, TRPCA)问题求得

(2)

其中分别代表范数以及核范数(会在第二节定义);为正则化参数,用于平衡低秩项和稀疏

项。图1展示矩阵和张量分解的联系与区别。

Figure 1. Illustration of matrix and tensor decomposition

图1. 矩阵和张量分解的图示

从理论上讲,并不是所有的张量都能够分解成稀疏和低秩两部分,比如当一个张量只有极少数的元素非零,而其余元素都为零时,这个“病态”张量就是既低秩又稀疏的,是不可能通过优化问题(2)将其分解为两个张量的。因此文献 [13] 给出张量核范数的定义和判断张量能否“病态”的非相关性条件,此外还提出了利用交替方向乘子法(Alternating Direction of Method of Multipliers, ADMM)来解决TRPCA问题。然后美中不足的是,尽管问题(2)是凸优化问题,可以在多项式时间内被解决,但是随着张量规模的扩大,计算时间也在成倍的增长:当张量的规模增长到时,甚至需要近四十多个小时才能够完成分解。从文献 [14] [15] 中可以知道,对于矩阵而言,不同的奇异值包含的矩阵的不同信息,而较小的奇异值所包含的信息量很少,而且大部分是观测噪声或者人为的结构信息,如果能舍弃掉部分较小的奇异值,可以明显提升运算效率,得到更优的解以及更好的去噪效果。

由于张量与矩阵结构和维度的不同,本文首先给出了张量的乘积,奇异值分解以及张量管秩、范数等定义。为了提高张量分解计算速度,受上述文献思想的启发,我们之后利用交替方向乘子法设计了一个基于截断核范数TRPCA算法,由于较大的奇异值已经包含了张量的主要信息,我们通过舍弃较小的奇异值来减少计算复杂度。最后本文通过对真实图片的恢复,证实了我们提出的方法的优势和有效性。

2. 张量的相关定义与运算

矩阵和张量在结构和维度上有较大的不同,为了方便区分以及后面的行文,本节会给出张量的相关定义以及张量的乘法、奇异值分解等运算法则。在本文中,我们分别用粗体小写字母,粗体大写字母和粗体手写体字母来表示向量,矩阵和张量。对于一个三维的张量,用来表示

位于张量位置上的元素;用来分别表示第i个水平切面,第j个侧面切片,第k个正面切片,特别地,也可以用来表示第k个正面切片。类似于矩阵,张量范数的定义如下:,不难看出,张量的第三个维度

时,张量的范数就会退化成矩阵范数。此外,我们还给出块循环矩阵和折叠、展开算子的定义:

, ,

定义1. (张量积) [16]:假设张量,则的张量乘积的规模为

定义2. (张量共轭转置) [16]:假设张量,记为其共轭转置张量,并且 其中表示矩阵的共轭矩阵。

定义3. (单位张量) [16]:如果一个张量,并且的第一个正面切片是一个的单位矩阵,其余正面切片全部为0,则称为单位张量。

定义4. (正交张量) [16]:称张量为正交张量,如果其满足

定义5:(F-对角张量) [16]:称为F-对角张量,如果的每一个正面切片均为对角矩阵。

定理1. (张量奇异值分解t-SVD) [16]:任意一个张量都可以被分解为

其中为正交张量,为F-对角张量。

定义6. (张量管秩) [17] 张量,其张量奇异值分解为,则的管秩定义为F-对角张量所有正面切片中最大的秩,即

定义7. (张量谱范数和核范数) [13] 设张量,其张量奇异值分解为,其谱范数和核范数分别记为

其中为块循环矩阵,r为定义6中的管秩。

至此我们给出了后面会涉及到的张量相关的定义与运算。张量可以视为矩阵的推广,对于三阶张量而言,每一个切片都可以视为矩阵;也可以把矩阵视为的特殊张量。矩阵与张量的有关运算类似又不尽相同,为此我们需要先了解张量的共轭转置、管秩、张量乘积以及张量奇异值分解等基本概念才方便我们进行后面优化算法的研究。

3. 主要模型及算法

3.1. 图像的低秩性

在实际生活和工作中,彩色图片随处可见,而绝大多数彩色图片都是以RGB的形式记录和储存的。具体来讲,RGB的彩色图片可以视为一个三阶张量,它的三个正面切片,分别代表红,绿,蓝三个通道。而且对于图片这样的可视数据,它极有可能是低秩的或者有着低秩的结构 [18],并且该图片的较大奇异值已经可以包含数据的原始信息,而较小的奇异值虽然并不严格等于零,但是非常接近零,这部分奇异值可能是观测,收集时带来的噪声,对图像的恢复作用并不是很大。为了验证图像中普遍存在的低秩结构,图2选取了三个不同规模的图片,并给出了其t-SVD分解后,第一个正面切片的奇异值。我们可以清楚地看到,图片奇异值最开始都非常的大,而后快速下降,并且越来越接近零,只有前面一小部分奇异值是显著大于零的。从这些不同清晰度的图片中也可以知道,无论图片分辨率的高低,这一奇异值的变化规律都是普遍存在的,即图片普遍都是具有低秩结构的。

Figure 2. (a & A) Image “Lenna” with dimension 512 × 512 × 3 and its singular. (b & B) Image “Landscape” with dimension 3225×2491×3 and its singular. (c & C) Image “Sunflowers” with dimension 5272 × 3997 × 3 and its singular

图2. 标准试验系统结果曲线(a和A)维度为512 × 512 × 3的图片“Lenna”以及它的奇异值。(b和B)维度为3225 × 2491 × 3的图片“Landscape”以及它的奇异值。(c和C) 维度为5272 × 3997 × 3的图片“Sunflowers”以及它的奇异值

3.2. 模型的建立与求解

受上述思想的启发,本文采用截断核范数的思想来解决张量鲁棒主成分分析问题,具体优化模型如下:

(3)

其中,表示张量奇异值的保留率,比如当时,表示保留观测张量前 的奇异值。由于张量的核范数是由其t-SVD分解后的第一个正面切片的奇异值之和定义的,所以这里只对进行截断。则该优化问题的增广拉格朗日函数为:

(4)

其中为惩罚参数,张量为新引入的拉格朗日乘子。ADMM方法处理多变量优化问题的核心思想上是在每一次计算中,仅选取其中一个为变量,其余均视为常数来处理,然后依次优化各个变量,最后经过多次迭代,满足收敛条件后停止。

1) 固定变量,更新

(5)

2) 固定变量,更新,类似的,我们有:

(6)

3) 固定变量,更新

(7)

4) 更新参数

(8)

通过上述的讨论,我们现在给出利用截断核范数来解决问题(4)的算法:

4. 实验结果与分析

张量鲁棒主成分分析在图像去噪,人脸识别等方面的应用极为广泛。因此,为了验证我们所提出的方法的有效性和优势,在本节中我们将会与另外两种在图像去噪上应用非常广泛的RPCA [5],SNN [19] 方法进行对比。因为RPCA只能处理矩阵数据,所以在恢复彩色图片时,我们将其用于依次恢复每一个正面切片,最后再合为一个张量。经过多次实验和调试,为了使每个方法都能取较好的恢复效果,我们

最终选取RPCA的参数,SNN的参数,我们的方法的参数。本文所有实验的实验环境均为Intel(R) Core i5-8250 CPU @ 1.60GHZ 处理器,

内存为4.00 GB,win10的计算机,在版本为R2016b的MATLAB上运行。

为了定量地比较各个方法之间的差异性,我们引入信噪比(PSNR)和结构相似性(SSIM)这两个指标来评价去噪后的图片效果,具体定义如下:

其中,分别表示原始张量和恢复张量;分别两个张量的代表局部均值,标准方差,互协方差以及每个像素值动态变化范围。这两种指标的数值越大,代表两个图片越接近,即恢复效果越好。

4.1. 参数δ的取值

在进行模拟实验时,我们引入的高斯噪声来构造污染后的观测张量,即从真实图片,随机选取20%的元素令其成为[0, 255]内的随机值。此外为了探究在去噪过程中,参数对我们恢复效果的影响,我们从[0.2, 0.95]中每间隔0.5进行取值,图3展示了参数奇异值选取率不同取值下,图片“Lenna”的恢复效果和恢复时间。

我们可以很直观的看出,随着奇异值的增大,PSNR值和所需要花费的时间都在逐渐增大,但是当时,时间的变化就不再明显;而时,PSNR值取得最大,因此在后面的实验中,我们都取

Figure 3. Recovery results of our method on image “Lenna” when corrupted rate, and singular value keeping rate varies from 0.2 to 0.95

图3. 当污染率时,奇异值保留率从0.2增长到0.95时,图片“Lenna”的恢复效果

4.2. 模拟实验结果及分析

为了研究各个方法在图像去噪时的表现,本小节会选取5张不同规模的彩色图片来进行实验,污染率仍为,并且被污染元素的位置和大小都是未知的,所以可以视为稀疏张量。并且前面已经说明过了,原始图像本身就是低秩的,因而可以把被污染的观测张量的去噪问题,视为TRPCA问题。各个方法的表现情况如图4所示:

Figure 4. Comparison of image recovery. (a) Original image; (b) corrupted image; (c)-(e) Recovered images by RPCA, SNN and Ours, respectively

图4. 图像恢复效果的比较。(a) 原始图片;(b) 被污染的图片;(c)-(e) 分别由RPCA,SNN和本文的方法得到的恢复图片

Table 1. Recovering result by RPCA, SNN and our method (PSNR/SSIM/Time)

表1. RPCA,SNN和我们的方法的恢复效果(PSNR/SSIM/Time)

表1展示上面五个图片恢复效果,包括PSNR,SSIM以及时间这三个指标的对比。从恢复效果来看,我们的方法取得的去噪效果最好,其次是SNN,RPCA的表现最差。以PSNR的平均值为例,我们的方法比RPCA高了2.75,我们从图4中也可以很直观地看出,(c)组图片有很明显的失真和不清晰,而用我们的方法去噪后图片会相对更加清晰,几乎看不到斑点等噪声。很有可能是因为RPCA没有考虑到张量的整体结构,而是简单地将其转化成矩阵来恢复。

SNN对于张量的恢复效果也很不错,但是我们的方法得到的PSNR和SSIM还是比SNN来得高。并且从时间上来看,SNN恢复所花的时间会更加的漫长,几乎是我们方法的两倍。如果是更加高清的图片,张量规模会更大,我们方法在时间复杂度上的优势会更加明显。

5. 总结与展望

本文在结合张量数据的高维结构和实际图片的低秩性,提出了利用截断核范数来解决张量鲁棒主成分分析问题,可以将一个被污染的张量分解成低管秩张量和稀疏张量,从而达到去噪的目的。张量的核范数由其奇异值之和定义的,而张量的较小奇异值包含的信息很少,可以将其舍弃,基于这个思想,我们通过约束奇异值的个数,来达到简化计算和提高恢复效果的目的。从实验中我们可以看出来,我们的方法可以用较小的时间取得很好的效果,优于使用也很广泛的SNN和RPCA模型。在之后的工作中,我们可以考虑大规模张量的恢复问题,寻求更好的核范数约束方式,以此来获得更好的去噪效果。

基金项目

中央高校基本科研业务费专项资金资助XDJK2018C076。

参考文献

[1] Litjens, G., Kooi, T., Bejnordi, B.E., et al. (2017) A Survey on Deep Learning in Medical Image Analysis. Medical Image Analysis, 42, 60-88.
https://doi.org/10.1016/j.media.2017.07.005
[2] Brubaker, S.W., Bonham, K.S., Zanoni, I., et al. (2015) Innate Immune Pattern Recognition: A Cell Biological Perspective. Annual Review of Immunology, 33, 257-290.
https://doi.org/10.1146/annurev-immunol-032414-112240
[3] Hancock, P.J.B., Burton, A.M. and Bruce, V. (1996) Face Processing: Human Perception and Principal Components Analysis. Memory & Cognition, 24, 26-40.
https://doi.org/10.3758/BF03197270
[4] Misra, J., Schmitt, W., Hwang, D., et al. (2002) Interactive Exploration of Microarraygene Expression Patterns in a Reduced Dimensional Space. Genome Research, 12, 1112-1120.
https://doi.org/10.1101/gr.225302
[5] Candes, E., Li, X., Ma, Y. and Wright, J. (2011) Robust Principal Component Analysis? Journal of the ACM, 58, Article No. 11.
https://doi.org/10.1145/1970392.1970395
[6] Liu, J., Musialski, P., Wonka, P. and Ye, J. (2013) Tensor Completion for Estimating Missing Values in Visual Data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 208-220.
https://doi.org/10.1109/TPAMI.2012.39
[7] Ji, H., Huang, S., Shen, Z. and Xu, Y. (2011) Robust Video Restoration by Joint Sparse and Low Rank Matrix Approximation. SIAM Journal on Imaging Sciences, 4, 1122-1142.
https://doi.org/10.1137/100817206
[8] Mørup, M. (2011) Applications of Tensor (Multiway Array) Factorizations and Decompositions in Data Mining. Data Mining and Knowledge Discovery, 1, 24-40.
https://doi.org/10.1002/widm.1
[9] Cao, W., Wang, Y., et al. (2016) Total Variation Regularized Tensor RPCA for Background Subtraction from Compressive Measurements. IEEE Transactions on Image Processing, 25, 4075-4090.
https://doi.org/10.1109/TIP.2016.2579262
[10] Kiers, H.A. (2000) Towards a Standardized Notation and Terminology in Multiway Analysis. Journal of Chemometrics: A Journal of the Chemometrics Society, 14, 105-122.
https://doi.org/10.1002/1099-128X(200005/06)14:3<105::AID-CEM582>3.0.CO;2-I
[11] Tucker, L.R. (1996) Some Mathematical Notes on Three-Mode Factor Analysis. Psychometrika, 31, 279-311.
https://doi.org/10.1007/BF02289464
[12] Hillar, C.J. and Lim, L.-H. (2013) Most Tensor Problems Are NP-Hard. Journal of the ACM, 60, 45.
https://doi.org/10.1145/2512329
[13] Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z. and Yan, S. (2016) Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, NV, 27-30 June 2016, 5249-5257.
https://doi.org/10.1109/CVPR.2016.567
[14] 谢瑞, 王春祥, 马会阳, 张永显. 等式约束病态模型的截断奇异值解及其统计性质[J]. 测绘科学技术学报, 2019, 36(3): 227-232+237.
[15] 王艺卓, 曾海金, 赵佳佳, 谢晓振. 基于张量截断核范数的高光谱图像超分辨率重构[J]. 激光与光电子学进展, 2019, 56(21): 80-89.
[16] Kilmer, M.E. and Martin, C.D. (2011) Factorization Strategies for Third-Order Tensors. Linear Algebra and Its Applications, 435, 641-658.
https://doi.org/10.1016/j.laa.2010.09.020
[17] Zhang, Z., Ely, G., Aeron, S., Hao, N. and Kilmer, M. (2014) Novel Methods for Multilinear Data Completion and Denoising Based on Tensor-SVD. 2014 IEEE Conference on Computer Vision and Pattern Recognition, Columbus, OH, 23-28 June 2014, 3842-3849.
https://doi.org/10.1109/CVPR.2014.485
[18] Hu, Y., Zhang D.B., Ye, J.P., et al. (2013) Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 2117-2130.
https://doi.org/10.1109/TPAMI.2012.271
[19] Huang, B., Mu, C., Goldfarb, D., et al. (2014) Provable Low-Rank Tensor Recovery. Optimization-Online, 4252, 455-500.