Advances in Applied Mathematics
Vol. 08  No. 08 ( 2019 ), Article ID: 31617 , 5 pages
10.12677/AAM.2019.88157

Enhanced Low Rank Tensor Approximation Algorithm

Tingting Ma, Xiaoting Feng

School of Mathematics, Liaoning Normal University, Dalian Liaoning

Received: Jul. 15th, 2019; accepted: Aug. 1st, 2019; published: Aug. 8th, 2019

ABSTRACT

In this paper, we extended the low rank matrix approximation problem to tensors. A method for estimating low-rank tensors by constructing convex optimization problems with non-convex regularization is proposed. The non-zero singular values are estimated by parameterized non-convex penalty functions, and the global optimal solution of the objective function is obtained. The experimental results show that this method can deal with the low rank tensor approximation problem very well and achieve image denoising.

Keywords:Nonconvex Regularization, Low Rank Tensor, Convex Optimization, Image Denoising

改进的低秩张量逼近算法

马婷婷,冯晓亭

辽宁师范大学数学学院,辽宁 大连

收稿日期:2019年7月15日;录用日期:2019年8月1日;发布日期:2019年8月8日

摘 要

本文在低秩矩阵逼近(Low-rank Matrix Approximation, LRMA)问题的基础上将其推广到张量上,提出了利用非凸正则化构造凸优化问题来估计低秩张量的方法,采用参数化的非凸罚函数估计非零的奇异值,并求出了该目标函数的全局最优解。实验结果表明,该方法能很好处理低秩张量逼近问题,实现图像去噪。

关键词 :非凸正则化,低秩张量,凸优化,图像去噪

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

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

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

1. 引言

近年来,低秩逼近广泛应用于信号处理 [1] [2] [3] 和机器学习 [4] [5] 等各个领域,研究人员提出了大量的方法,这些算法大致分为两种,凸优化算法和非凸优化算法。凸优化算法,主要利用核范数极小化。这一思路由文献 [6] 提出,主要包括:文献 [7] 提出的奇异值阈值(Singular Value Thresholding, SVT)算法。这种算法对原始矩阵的不同奇异值的惩罚力度相同,所求出的全局最优解在实际问题中效果差。所以本文提出了一个新的算法,即利用非凸正则化构造凸优化问题来估计低秩张量。该方法不仅能很好处理低秩张量逼近问题,还能实现图像去噪。

2. 预备知识

定义1 (张量的切片)对于一个三阶张量 A i j k ,用 A ( i , : , : ) , A ( : , i , : ) , A ( : , : , i ) 分别表示张量 A 第i个水平的,侧面的和正面的切片,通常记正面切片 A ( i ) = ( : , : , i )

定义2 (离散傅里叶变换)设张量 A R n 1 × n 2 × n 3 沿着第三维度的傅里叶变换得到 A ¯ C n 1 × n 2 × n 3 ,在傅里叶变换域中块循环矩阵可以被映射到傅里叶变换域的一个块对角矩阵。

记 块循环矩阵为

b c i r c ( A ) = [ A ( 1 ) A ( n 3 ) A ( 2 ) A ( 2 ) A ( 1 ) A ( 3 ) A ( n 3 ) A ( n 3 1 ) A ( 1 ) ] C n 1 n 3 × n 2 n 3 (1)

记 块对角矩阵为

A ¯ = b d i a g ( A ¯ ) = [ A ¯ ( 1 ) A ¯ ( 2 ) A ¯ ( n 3 ) ] C n 1 n 3 × n 2 n 3 (2)

定义3 [8] (张量的核范数)令 A = U S V ,则有

A = S , I = i = 1 r S ( i , i , 1 ) (3)

其中 I 表示单位张量, r = r a n k t ( A )

假设1 [9] :非凸性惩罚函数 ϕ : R R 满足以下条件:

1) ϕ 在R上连续并且 ϕ R / { 0 } 上是连续可微的且为偶函数即 ϕ ( x ; a ) = ϕ ( x ; a )

2) ϕ ( x ; a ) 0 , a > 0

3) ϕ ( x ; a ) 0 , a > 0 (4)

4) ϕ ( 0 ; a ) = 1

5) inf X 0 ϕ ( x ; a ) = ϕ ( 0 + ; a ) = a

定理1 [8] (张量奇异值分解,T-SVD)令 A R n 1 × n 2 × n 3 ,可以将其分解为

A = U S V (5)

其中 U R n 1 × n 1 × n 3 V R n 2 × n 2 × n 3 都是正交张量, S R n 1 × n 2 × n 3 是F-对角张量。

定理 2 [9] 令 Y = U Σ V T 为Y的奇异值SVD分解,假设 ϕ R R 上的满足假设1的非凸惩罚函数,当 0 a < 1 λ 时, 1 2 Y X F 2 + λ i = 1 k ϕ ( σ i ( X ) , a ) 的全局最小值为

X ¯ = U Θ ( Σ ; λ , a ) V T (6)

其中 Θ ( y ; λ , a ) : = arg min x R { 1 2 ( y x ) 2 + λ ϕ ( x ; a ) } 是函数 ϕ 的近端算子。

3. 改进的低秩张量逼近算法

3.1. 模型的建立

Y 为受到噪声污染后的低秩张量, X 为潜在的目标低秩张量, E 为高斯噪声张量。则有 Y = X + E 。所以低秩张量逼近模型如下:

arg min X { Ψ ( X ) = 1 2 Y X F 2 + λ i = 1 k ϕ ( S ( i , i , 1 ) , a ) } (7)

本文假设所有张量都是三阶张量即 X R n 1 × n 2 × n 3 , Y R n 1 × n 2 × n 3 。其中 k = min ( n 1 n 3 , n 2 n 3 ) ϕ 是稀疏产生的正则化函数,所以它可能是非凸的。 S ( i , i , 1 ) 表示张量 X 奇异值分解后F-对角张量的第一个正面切面。

3.2. 模型的求解

由式(1)可得 i = 1 r S ( i , i , 1 ) = A 则有 λ i = 1 k ϕ ( S ( i , i , 1 ) , a ) = λ ϕ ( A , a ) (8)

可以得到目标函数的如下形式:

1 2 [ 1 n 3 Y ¯ F 2 + X ¯ F 2 2 1 n 3 Y ¯ , X ¯ ] + λ ϕ ( X , a ) (9)

由张量核范数与矩阵核范数之间的关系,所以目标函数可以写成如下形式:

1 2 n 3 Y ¯ X ¯ F 2 + 1 n 3 λ ϕ ( X ¯ , a ) = 1 n 3 [ 1 2 Y ¯ X ¯ F 2 + λ i = 1 k ϕ ( σ i ( X ¯ ) , a ) ] (10)

式中 X ¯ , Y ¯ R n 1 n 3 × n 2 n 3 σ i 表示矩阵 X ¯ 的第i个奇异值, k = min ( n 1 n 3 , n 2 n 3 )

根据定理2可以得到目标函数的最优解为

1 n 3 ( U Θ ( Σ ; λ , a ) V T ) (11)

其中 Θ ( Σ ; λ , a ) : = arg min X R { 1 2 ( Σ X ) 2 + λ ϕ ( X ; a ) }

4. 实验

对于一个噪声图像 Y ,将其进行奇异值分解后得到的F-对角张量的第一个正面切片记为Y,通过块匹配方法可以得到非局部自相似块矩阵 Y j ,则有 Y j = X j + W j ,其中 X j W j 分别表示清晰图像和高斯噪声。通过叠加这些非局部的相似块形成张量,为了从 Y j 中提取出 X j ,我们构造了如下目标函数:

X ^ j : = arg min X { 1 2 Y j X F 2 + λ i = 1 m ϕ ( S ( i , i , 1 ) ; a ) } (10)

根据定理2可得到(10)的最优解为 X ^ j = 1 n 3 ( U j Θ ( Σ j ; λ , a ) V j T )

Figure 1. Comparison of denoising effects of different methods

图1. 不同方法去噪效果对比

图1显示了使用不同的方法对噪声图像进行去噪的结果。表1列出了三种测试图像的平均PSNR值和运行时间。所提出的LRTA方法与BM3D、PS和WNNM方法相比可以获得更高的PSNR。在图像质量方面,所提出的LRTA方法也更为清晰一些。

Table 1. PSNR values and run time data

表1. PSNR值和运行时间数据

5. 结论

本文提出了一种新的方法来估计低秩张量。尽管正则化项不是凸的,但所提出的目标函数是凸的。通过对输入张量进行离散的傅里叶变换后再进行奇异值分解,得到F-对角张量的第一个正面切面形成的矩阵的奇异值进行阈值化,得到目标函数的非迭代解。在基于非局部自相似的图像去噪算法中,证明了该方法的有效性。

文章引用

马婷婷,冯晓亭. 改进的低秩张量逼近算法
Enhanced Low Rank Tensor Approximation Algorithm[J]. 应用数学进展, 2019, 08(08): 1336-1340. https://doi.org/10.12677/AAM.2019.88157

参考文献

  1. 1. Nadakuditi, R.R. (2014) OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Da-ta-Driven Singular Value Shrinkage. IEEE Transactions on Information Theory, 60, 3002-3018. https://doi.org/10.1109/TIT.2014.2311661

  2. 2. Markovsky, I. (2008) Structured Low-Rank Approximation and Its Applications. Automatica, 44, 891-909. https://doi.org/10.1016/j.automatica.2007.09.011

  3. 3. Nguyen, H.M., Peng, X., Do, M.N. and Liang, Z.P. (2013) Denoising MR Spectroscopic Imaging Data with Low-Rank Approximations. IEEE Transactions on Biomedical Engi-neering, 60, 78-89. https://doi.org/10.1109/TBME.2012.2223466

  4. 4. Drineas, P., Kannan, R., and Mahoney, M.W. (2006) Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. SIAM Journal on com-puting, 36, 158-183. https://doi.org/10.1137/S0097539704442696

  5. 5. Kannan, R. and Vempala, S. (2009) Spectral Algorithms. Foundations and Trends in Theoretical Computer Science, 4, 157-288. https://doi.org/10.1561/0400000025

  6. 6. Candes, E.J. and Recht, B. (2008) Exact Low-Rank Matrix Completion via Convex Optimization. 2008 46th Annual Allerton Conference on Communication, Control, and Computing, Urba-na-Champaign, IL, 23-26 September 2008, 806-812. https://doi.org/10.1109/ALLERTON.2008.4797640

  7. 7. Cai, J.F., Candes, E.J. and Shen, Z.W. (2010) A Singular Value Thresholding Algorithm for Matrix Completion. SIAM Journal on Optimization, 20, 1956-1982. https://doi.org/10.1137/080738970

  8. 8. Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z. and Yan, S. (2018) Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1. https://doi.org/10.1109/TPAMI.2019.2891760

  9. 9. Parekh, A. and Selesnick, I.W. (2016) Enhanced Low-Rank Matrix Approximation. IEEE Signal Processing Letters, 23, 493-497. https://doi.org/10.1109/LSP.2016.2535227

期刊菜单