含t-积结构的张量广义Krylov子空间方法求解线性离散不适定问题.pdf

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(1),208-216 Published Online January 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.131024 文章引用文章引用:王仕伟.含t-积结构的张量广义Krylov子空间方法求解线性离散不适定问题J.应用数学进展,2024,13(1):208-216.DOI:10.12677/aam.2024.131024 含含t-积结构的张量广义积结构的张量广义Krylov子空间方法求解子空间方法求解线性离散不适定问题线性离散不适定问题 王仕伟王仕伟 成都理工大学数理学院，四川 成都 收稿日期：2023年12月17日；录用日期：2024年1月11日；发布日期：2024年1月17日 摘摘 要要 本文讨论了基于三阶张量的本文讨论了基于三阶张量的t-积形式，将积形式，将广义广义Krylov子空间方法在解决子空间方法在解决大规模大规模线性离散不适定问题中的线性离散不适定问题中的应用应用。针对于离散不适定问题，首先确定正则化参数，并将一系列投影应用到广义的。针对于离散不适定问题，首先确定正则化参数，并将一系列投影应用到广义的Krylov子空间上。子空间上。数据张量是一般的三阶张量或由横向定向矩阵定义的张量。在数值例子和彩色图像修复中的应用说明了数据张量是一般的三阶张量或由横向定向矩阵定义的张量。在数值例子和彩色图像修复中的应用说明了该方法的有效性。该方法的有效性。关键词关键词 离散不适定问题，广义离散不适定问题，广义Krylov子空间子空间，t-积，正则化积，正则化 The Tensor Generalized Krylov Subspace Method with t-Product Structure for Solving Linear Discrete Ill-Posed Problems Shiwei Wang College of Mathematics and Physics,Chengdu University of Technology,Chengdu Sichuan Received:Dec.17th,2023;accepted:Jan.11th,2024;published:Jan.17th,2024 Abstract This article discusses the application of the generalized Krylov subspace method in solving large-scale linear discrete ill-posed problems based on the t-product form of third-order tensors.For discrete ill-posed problems,the regularization parameters are first determined,and a series of projections are applied to the generalized Krylov subspace.A data tensor is a general third-order 王仕伟 DOI:10.12677/aam.2024.131024 209 应用数学进展 tensor or a tensor defined by a transversely oriented matrix.The application of this method in numerical examples and color image restoration demonstrates its effectiveness.Keywords Discrete Ill-Posed Problems,Generalized Krylov Subspaces,t-Product,Regularization Copyright 2024 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.引言引言 具有张量形式的线性离散不适定问题是彩色图像复原、视频去模糊、目标识别、层析成像图像重建等领域的共性问题，是数值代数的一个重要研究内容之一。许多图像恢复方法通过叠加表示图像的矩阵元素来对每个图像进行向量化。矩阵条目表示编码灰度值的像素值。每一帧表示一个图像，因此，一个视频可以被表示为一个长向量，每个条目表示某一帧中的一个像素值。然而，这种表示破坏了原始视频帧可能拥有的空间相关性和结构复杂性。具有 t-积结构的三阶张量系统由 Kilmer 等人1提出，该系统避免了矩阵化和向量化，保留了多维结构。t-乘积已被证明有用的应用领域包括面部识别2、层析图像重建3、视频补全4和图像分类5。用 t-积求解大规模离散线性不适定问题的方法有很多。Kilmer 等人2提出了一种张量共轭梯度(t-CG)方法以求解张量线性系统=?的最小二乘问题。Zhang 等人6提出了计算超大数据集的随机张量奇异值分解(rtSVD)方法，在图像数据压缩和分析方面具有应用前景。Ugwu和 Reichel 7提出了一种新的随机张量奇异值分解(R-tSVD)，该方法改进了1中的截断张量奇异值分解(T-tSVD)。Guide 等人8开发了张量 T-全局 GMRES 算法和张量 T-全局 Golub-Kahan 算法，并使用季洪诺夫正则化技术获得了有效的正则化解。最近，Reichel 等人引入了张量 Golub-Kahan 双对角化方法9、张量 Arnoldi-Tikhonov 和张量 GMRES-type 10，通过将大尺度问题简化为小尺度问题来解决大规模线性不适定问题。Lampe 等人11开发了广义 Krylov 子空间(GKS)方法来求解大规模 Tikhonov 正则化问题。2.预备知识预备知识 对于三阶张量l m n?，图 1 显示了正面切片():,:,k、横向切片():,:j和管(),:i j。为了简化，我们缩写为():,:,kkA=。在 t-积的定义中广泛地使用循环矩阵 T0123vvvvv=，则()0321103221033210circvvvvvvvvvvvvvvvvv=是一个循环矩阵。循环矩阵可以用归一化离散傅里叶变换(DFT)矩阵，它是酉矩阵。特别地，如果 v是1n，nF是nnDFT 矩阵，nF是它的共轭转置，则()circnnFv F Open AccessOpen Access王仕伟 DOI:10.12677/aam.2024.131024 210 应用数学进展 是对角的。从一个张量的切片中创建一个块循环矩阵。假设块循环是由张量正面切片创建的，我们利用上面的例子得到块循环矩阵()112213121bcircnnnnnAAAAAAAAAAAA=?.一个lnm矩阵由()unfold 得到，而算子 fold 将这个矩阵折叠回张量，即，()()()12unfold,fold unfold.nAAA=?定义定义 给定两个张量l m n?和m p n?，它们之间的 t-积被定义为()()()fold bcircunfold,=这里l p n?。(a)(b)(c)Figure 1.(a)Frontal slices():,:,k;(b)Lateral slices():,:j;(c)Tube fibers(),:i j 图图 1.(a)正面切片():,:,k；(b)横向切片():,:j；(c)管(),:i j 张量 QR(tQR)的分解由 Kilmer 等人12描述。l m n?的 QR 分解表示为,=其中张量l m n?是部分正交的，m m n?的每个正面切片是一个上三角形。算法 1 的 tQR 分解是在傅里叶域实现 tQR 分解。算法算法 1.tQR 分解1 输入：l m n?输出：,l m nm m n =?()fft,3=For 1,2,kn=?():,:,kQR=()():,:,:,:,kQkR=End ()ifft,3=，()ifft,3=王仕伟 DOI:10.12677/aam.2024.131024 211 应用数学进展 表 1 是本文所使用的符号的说明，Table 1.Symbol description 表表 1.符号说明 符号 说明说明*t-积 张量 T 张量的转置 张量的 Moore-Penrose 广义逆 F 张量的 Frobenius 范数 1 张量的逆():,:,jj?的第 j 个张量列，的第 j 个侧向片 单位张量 3.张量张量 Tikhonov 正则化方法正则化方法 本文旨在求解张量 t-积结构的线性系统 ,1,1,l m nl m nlni j kalm =?(3.1)和最小二乘问题 12min.mnF?(3.2)张量的管秩的确定不明，即很难有意义地定义的管秩。具体地说，的奇异管的 Frobenius 范数随指数数的增加而迅速衰减为零。特别地，它的许多奇异管以不同数量级的微小 Frobenius 范数的形式存在，使得最小化变得离散不适定，此时称问题(3.1)为张量离散线性不适定问题。它们产生于彩色图像和视频的恢复，如1 9 10。一般情况下，不适定问题(3.1)的右端张量列?是观察得到的数据，假设ture?是一个未知的、不可用的张量列，则真实解对应的线性方程为tureture=?，在问题(3.1)中，ture?被噪声1mn?污染，即，.true=+?由于的某些正面切片的条件数很大以及?中噪声?的影响，它的直接解是没有意义的。正则化通常是用来减少(3.1)的病态性的影响。我们考虑 Tikhonov 正则化，并替换问题(3.1)为张量惩罚最小二乘问题 122argmin,mnFF+?(3.3)这里的0为正则化参数。最小化问题(3.3)的正规方程为()TT.+=?(3.4)4.张量广义张量广义 Krylov 子空间方法子空间方法 本文将矩阵形式的广义 Krylov 子空间(GKS)方法推广到具有 t-积结构的三阶张量系统中，得到了张量广义 Krylov 子空间投影方法(tGKS)。考虑了 tGKS 方法来构造(3.4)的子空间。我们在解空间中构造了王仕伟 DOI:10.12677/aam.2024.131024 212 应用数学进展 一组基m k nk?，用张量列1mnj?表示为 12,.kk=?定理定理 假设在 t-积结构中，()表示张量的零空间，当问题(3.3)满足()(),=?且0，最小化问题(3.3)有一个唯一的解()1TT.=+?定理证明详见文献9。使()kkn=?，则可获得(3.3)的变体 1221argminknkkFF+?.(4.1)k是张量列正交的，且满足Tkk=，正规方程(3.4)到子空间k中的投影可以表示为()TT1TT.kkk+=?(4.2)将0设置为一个可用的正则化参数，可以得到()()1TT1TT.kkk=+?(4.3)直接计算(4.3)的代价是昂贵的，由于张量的数据量过大，整体计算()TT1kk+的 t-积的逆会占据过多内存，一种合理的考虑是将k进行分解，可使用张量 QR(tQR)分解。即使得,kAA=则可得到()T1TTT.AAkkAA+=?(4.4)对于(4.4)的解并结合k=?，获得(3.4)的残差()T1T.kkk=+?(4.5)在更新搜索空间k过程中，不可避免地会出现一个舍入错误。为了增强正交性，将k重新正交化用于更新k。因此()()T111,Normalize,.,kkkkkkkkk+=?(4.6)方程(3.1)为标准形式，k的张量列构成 k 维张量 Krylov 子空间的标准正交基()()()TTTTTTT1,.kkspan+=?综合(3.1)(4.6)，得到了算法 2 的张量广义 Krylov 子空间-Tikhonov 方法(tGKS-T)。算法算法 2.tGKS-T 输入：,60maxk=?，输出：近似解*k?()TT.+=?()()T111,tQR,TNormalize=?王仕伟 DOI:10.12677/aam.2024.131024 213 应用数学进展 续表 For 1,2,k=?until maxkk=or 6110kF+。本文设定的噪音水平在实际计算中设为不可知，正则化参数通过多次实验得到一个合理值，有关正则化参数可以通过 L-曲线，差异原理等方式确定，而正则化参数的合理设定以及求解已远远超出本文范围，本文不再讨论。表 2 给出了在不同噪声水平下由 tGKS 方法和一般矩阵系统的广义 Krylov 子空间方法(GKS)计算出的信噪比和相对误差，所需的迭代次数(子空间维数 k)，以及计算时间。表中的数据显示 tGKS 方法的恢复效果优于 GKS。tGKS 方法使用了比 GKS 更多的时间，但 tGKS 只需要构造少数的子空间，且得到的解的相对误差kE与 SNR 都优于 GKS，这是由于 tGKS 的张量 t-积结构可以整体考虑数据。Table 2.Result of example 5.1 表表 2.例子 5.1 结果 方法 子空间维数 k kE SNR 时间/秒(s)102 GKS 0.5 48 3.21e02 0.86e+02 2.13 tGKS 0.5 4 2.10e02 0.98e+02 8.41 103 GKS 0.1 41 6.62e02 1.31e+02 1.10 tGKS 0.1 2 4.10e03 1.33e+02 4.12 例子例子 5.2 彩色图像恢复 此示例显示了模糊彩色图像 Lena 在 tGKS 方法下的恢复情况。在 MATLAB 中原始图像数据存储为张量256 256 3ori?，并将这个张量转换为张量256 3 256true?，设置256,3N=和 band=12，定义256 256 256?，其中()()8:,:,10kcond，12k，即，()()()()()()()22:,:,0:12,1,1,1,1,256.2izexpbandzerosNbandAtoeplitz zA iA i=?Table 3.Result of Example 5.2 表表 3.例子 5.2 结果 方法 子空间维数 k kE SNR 时间/秒(s)102 GKS 0.5 81 8.51e02 12.96 20.69 tGKS 0.5 27 7.46e02 13.84 96.63 103 GKS 0.1 68 7.33e03 13.96 21.36 tGKS 0.1 29 6.50e03 15.65 180.69 表 3 显示了例子 5.2 的在不同噪音水平下的结果，在噪音水平较小时，所需要的迭代时间更多，这是由于在更小的噪音水平的系统中进行迭代时，要达到设置的收敛条件需要更多次迭代，可以得到更精确的迭代解，因此当满足设置的算法停止标准时，更小的噪音水平的系统的迭代时间虽然更长，但得到的解更精确。矩阵系统的 GKS 方法在 MATLAB 上进行彩色图像的恢复实验中，通常是将彩色图像三通道进行矩阵平展开后进行矢量化，这样的方式意味着要建立更多的子空间。王仕伟 DOI:10.12677/aam.2024.131024 215 应用数学进展 而 tGKS 方法的张量 t-积考虑了彩色图像三通道之间可能存在的空间结构性，从整体上对模糊和加噪的彩色图像进行恢复，建立了比 GKS 方法少的子空间，恢复效果也优于 GKS 方法。图 2 给出了彩色图像 Lena 和被模糊加了噪音的图像，以及 tGKS 方法和 GKS 方法下的恢复图像。Figure 2.The restoration effect of color images in Table 3 with 310=图图 2.表 3 中310=时，彩色图像的恢复效果图 6.结论结论 相对于传统方法，即将模糊图像进行矩阵化或者向量化，张量 t-积结构考虑了各个通道间的空间结构性。本文介绍的含 t-积结构的张量广义 Krylov 子空间方法在求解离散不适定问题时，建立的 Krylov 子空间维数较少，通过说明例证明了所提出的方法在数值计算和图像恢复应用中的有效性。值得注意的是，tGKS 方法通过相对误差和信噪比值评估，提供了图像恢复算法性能的综合评估，在图像恢复和视频恢复上显示出显著的潜力。基金项目基金项目 四川省中央引导地方科技发展专项项目(2022ZYD0008)。参考文献参考文献 1 Kilmer,M.E.and Martin,C.D.(2011)Factorization Strategies for Third Order Tensors.Linear Algebra and Its Appli-cations,435,641-658.https:/doi.org/10.1016/j.laa.2010.09.020 2 Hao,N.,Kilmer,M.E.,Braman,K.and Hoover,R.C.(2013)Facial Recognition Using Tensor-Tensor Decompositions.SIAM Journal on Imaging Sciences,6,437-463.https:/doi.org/10.1016/j.laa.2010.09.020 3 Soltani,S.,Kilmer,M.E.and Hansen,P.C.(2016)A Tensor-Based Dictionary Learning Approach to Tomographic Image Reconstruction.BIT Numerical Mathematics,56,1425-1454.https:/doi.org/10.1007/s10543-016-0607-z 4 Zhang,Z.,Ely,G.,Aeron,S.,Hao,N.and Kilmer,M.E.(2013)Novel Factorization Strategies for Higher Order Ten-sors:Implications for Compression and Recovery of Multi-Linear Data.arXiv Preprint.https:/arxiv.org/pdf/1307.0805.pdf 王仕伟 DOI:10.12677/aam.2024.131024 216 应用数学进展 5 Newman,E.,Kilmer,M.and Horesh,L.(2017)Image Classification Using Local Tensor Singular Value Decomposi-tions.2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing(CAMSAP),Curacao,10-13 December 2017,1-5.https:/doi.org/10.1109/CAMSAP.2017.8313137 6 Zhang,J.,Saibaba,A.K.,Kilmer,M.E.and Aeron,S.(2018)A Randomized Tensor Singular Value Decomposition Based on the t-Product,Numer.Linear Algebra and Its Applications,25,e2179.https:/doi.org/10.1002/nla.2179 7 Ugwu,U.O.and Reichel,L.(2021)Tensor Regularization by Truncated Iteration:A Comparison of Some Solution Methods for Large-Scale Linear Discrete Ill-Posed Problem with a t-Product.arXiv preprint arXiv:2110.02485.8 El Guide,M.,El Ichi,A.,Jbilou,K.and Sadaka,R.(2021)On Tensor GMRES and Golub-Kahan Methods via the t-Product for Color Image Processing.Electronic Journal of Linear Algebra,37,524-543.https:/doi.org/10.13001/ela.2021.5471 9 Reichel,L.and Ugwu,U.O.(2022)The Tensor Golub-Kahan-Tikhonov Method Applied to the Solution of Ill-Posed Problems with At-Product Structure.Numerical Linear Algebra with Applications,29,e2412.https:/doi.org/10.1002/nla.2412 10 Ugwu,U.O.and Reichel,L.(2022)Tensor Arnoldi-Tikhonov and GMRES-Type Methods for Ill-Posed Problems with a t-Product Structure.Journal of Scientific Computing,90,Article No.59.https:/doi.org/10.1007/s10915-021-01719-1 11 Lampe,J.,Reichel,L.and Voss,H.(2012)Large-Scale Tikhonov Regularization via Reduction by Orthogonal Projec-tion.Applications of Linear Algebra,436,2845-2865.https:/doi.org/10.1016/j.laa.2011.07.019 12 Kilmer,M.E.,Misha,K.,Hao,N.and Hoover,R.C.(2013)Third-Order Tensors as Operators on Matrices:A Theoret-ical and Computational Framework with Applications in Imaging.SIAM Journal on Matrix Analysis and Applications,34,148-172.https:/doi.org/10.1137/110837711 13 Hansen,P.C.(2007)Regularization Tools,Version 4.0 for Matlab 7.3.Numerical Algorithms,46,189-194.https:/doi.org/10.1007/s11075-007-9136-9