research-article

Tensor Arnoldi–Tikhonov and GMRES-Type Methods for Ill-Posed Problems with a t-Product Structure

Authors:

Lothar Reichel,

Ugochukwu O. UgwuAuthors Info & Claims

Journal of Scientific Computing, Volume 90, Issue 1

https://doi.org/10.1007/s10915-021-01719-1

Published: 01 January 2022 Publication History

Abstract

This paper describes solution methods for linear discrete ill-posed problems defined by third order tensors and the t-product formalism introduced in (Linear Algebra Appl 435:641–658, 2011). A t-product Arnoldi (t-Arnoldi) process is defined and applied to reduce a large-scale Tikhonov regularization problem for third order tensors to a problem of small size. The data may be represented by a laterally oriented matrix or a third order tensor, and the regularization operator is a third order tensor. The discrepancy principle is used to determine the regularization parameter and the number of steps of the t-Arnoldi process. Numerical examples compare results for several solution methods, and illustrate the potential superiority of solution methods that tensorize over solution methods that matricize linear discrete ill-posed problems for third order tensors.

References

[1]

Beik FPA, Jbilou K, Najafi-Kalyani M, and Reichel L Golub–Kahan bidiagonalization for ill-conditioned tensor equations with applications Numer. Algorithms 2020 84 1535-1563

[2]

Beik FPA, Najafi-Kalyani M, and Reichel L Iterative Tikhonov regularization of tensor equations based on the Arnoldi process and some of its generalizations Appl. Numer. Math. 2020 151 425-447

[3]

Buccini A, Pasha M, and Reichel L Generalized singular value decomposition with iterated Tikhonov regularization J. Comput. Appl. Math. 2020 373 112276

[4]

Calvetti D, Lewis B, and Reichel L On the regularizing properties of the GMRES method Numer. Math. 2002 91 605-625

[5]

Calvetti D, Morigi S, Reichel L, and Sgallari F Tikhonov regularization and the L-curve for large, discrete ill-posed problems J. Comput. Appl. Math. 2000 123 423-446

[6]

Calvetti D and Reichel L Tikhonov regularization of large linear problems BIT Numer. Math. 2003 43 263-283

[7]

Donatelli M, Martin D, and Reichel L Arnoldi methods for image deblurring with anti-reflective boundary conditions Appl. Math. Comput. 2015 253 135-150

[8]

El Guide, M., El Ichi, A., Jbilou, K., Beik, F.P.: Tensor GMRES and Golub–Kahan bidiagonalization methods via the Einstein product with applications to image and video processing. https://arxiv.org/pdf/2005.07458.pdf

[9]

El Ichi, M., El Guide, A., Jbilou, K.: Discrete cosine transform LSQR and GMRES methods for multidimensional ill-posed problems. https://arxiv.org/pdf/2103.11847.pdf (2021)

[10]

El Guide, M., El Ichi, A., Jbilou, K., Sadaka, R.: Tensor Krylov subspace methods via the T-product for color image processing. https://arxiv.org/pdf/2006.07133.pdf (2020)

[11]

Ely, G., Aeron, S., Hao, N., Kilmer, M.E.: 5d and 4d pre-stack seismic data completion using tensor nuclear norm (TNN). In: SEG International Exposition and Eighty-Third Annual Meeting at Houston, TX (2013)

[12]

Engl HW, Hanke M, and Neubauer A Regularization of Inverse Problems 1996 Dordrecht Kluwer

[13]

Fenu C, Reichel L, and Rodriguez G GCV for Tikhonov regularization via global Golub–Kahan decomposition Numer. Linear Algebra Appl. 2016 23 467-484

[14]

Gazzola S, Novati P, and Russo MR On Krylov projection methods and Tikhonov regularization Electron. Trans. Numer. Anal. 2015 44 83-123

[15]

Golub GH, Heath M, and Wahba G Generalized cross-validation as a method for choosing a good ridge parameter Technometrics 1979 21 215-223

[16]

Hansen PC Analysis of discrete ill-posed problems by means of the L-curve SIAM Rev. 1992 34 561-580

[17]

Hansen PC Regularization tools version 4.0 for MATLAB 7.3 Numer. Algorithms 2007 46 189-194

[18]

Hao N, Kilmer ME, Braman K, and Hoover RC Facial recognition using tensor-tensor decompositions SIAM J. Imaging Sci. 2013 6 437-463

[19]

Huang G, Reichel L, and Yin F On the choice of subspace for large-scale Tikhonov regularization problems in general form Numer. Algorithms 2019 81 33-55

[20]

Kernfeld E, Kilmer M, and Aeron S Tensor-tensor products with invertible linear transforms Linear Algebra Appl. 2015 485 545-570

[21]

Kilmer, M., Braman, K., Hao, N.: Third order tensors as operators on matrices: a theoretical and computational framework. Technical Report, Department of Computer Science, Tufts University (2011)

[22]

Kilmer ME, Braman K, Hao N, and Hoover RC Third-order tensors as operators on matrices: a theoretical and computational framework with applications in imaging SIAM J. Matrix Anal. Appl. 2013 34 148-172

[23]

Kilmer ME and Martin CD Factorization strategies for third-order tensors Linear Algebra Appl. 2011 435 641-658

[24]

Kindermann S Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems Electron. Trans. Numer. Anal. 2011 38 233-257

[25]

Kindermann S and Raik K A simplified L-curve method as error estimator Electron. Trans. Numer. Anal. 2020 53 217-238

[26]

Kolda TG and Bader BW Tensor decompositions and applications SIAM Rev. 2009 51 455-500

[27]

Lewis B and Reichel L Arnoldi–Tikhonov regularization methods J. Comput. Appl. Math. 2009 226 92-102

[28]

Lu C, Feng J, Chen Y, Liu W, Lin Z, and Yan S Tensor robust principal component analysis with a new tensor nuclear norm IEEE Trans. Pattern Anal. Mach. Intell. 2020 42 925-938

[29]

Lund, K.: The tensor t-function: a definition for functions of third-order tensors. arXiv preprint. arXiv:1806.07261 (2018)

[30]

Martin CD, Shafer R, and LaRue B An order-

p

tensor factorization with applications in imaging SIAM J. Sci. Comput. 2013 35 A474-A490

[31]

Miao Y, Qi L, and Wei Y T-Jordan canonical form and T-Drazin inverse based on the T-product Commun. Appl. Math. Comput. 2021 3 201-220

[32]

Miao Y, Qi L, and Wei Y Generalized tensor function via the tensor singular value decomposition based on the T-product Linear Algebra Appl. 2020 590 258-303

[33]

Neubauer A Augmented GMRES-type versus CGNE methods for the solution of linear ill-posed problems Electron. Trans. Numer. Anal. 2019 51 412-431

[34]

Reichel L and Shyshkov A A new zero-finder for Tikhonov regularization BIT Numer. Math. 2008 48 627-643

[35]

Reichel, L., Ugwu, U.O.: The tensor Golub–Kahan–Tikhonov method applied to the solution of ill-posed problems with a t-product structure. Numer. Linear Algebra Appl. 29,(2022). https://doi.org/10.1002/nla.2412

[36]

Reichel L and Rodriguez G Old and new parameter choice rules for discrete ill-posed problems Numer. Algorithms 2013 63 65-87

[37]

Saad Y Iterative Methods for Sparse Linear Systems 2003 2 Philadelphia SIAM

[38]

Saad Y and Schultz MH GMRES: a generalized minimal residual method for solving nonsymmetric linear systems SIAM J. Sci. Stat. Comput. 1986 7 856-869

[39]

Savas B and Eldén L Krylov-type methods for tensor computations Linear Algebra Appl. 2013 438 891-918

[40]

Soltani S, Kilmer ME, and Hansen PC A tensor-based dictionary learning approach to tomographic image reconstruction BIT Numer. Math. 2015 56 1425-1454

[41]

Trefethen LN and Bau D III Numerical Linear Algebra 1997 Philadelphia SIAM

[42]

Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M. E.: Novel methods for multilinear data completion and de-noising based on tensor-SVD. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23–28, 2014, pp. 3842–3849 (2014)

Cited By

Liu YZhao XDing MWang JJiang THuang T(2024)The Generalized Tensor Decomposition with Heterogeneous Tensor Product for Third-Order TensorsJournal of Scientific Computing10.1007/s10915-024-02637-8100:3Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1007/s10915-024-02637-8
Fan MLi J(2024)The Order-p Tensor Linear Complementarity Problem for Images DeblurringJournal of Scientific Computing10.1007/s10915-024-02502-899:2Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/s10915-024-02502-8
Lund KSchweitzer M(2023)The Fréchet derivative of the tensor t-functionCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-023-00527-360:3Online publication date: 16-Jun-2023
https://dl.acm.org/doi/10.1007/s10092-023-00527-3
Show More Cited By

Index Terms

Tensor Arnoldi–Tikhonov and GMRES-Type Methods for Ill-Posed Problems with a t-Product Structure

Index terms have been assigned to the content through auto-classification.

Recommendations

Tensor Krylov subspace methods with an invertible linear transform product applied to image processing
Abstract
This paper discusses several transform-based methods for solving linear discrete ill-posed problems for third order tensor equations based on a tensor-tensor product defined by an invertible linear transform. Linear transform-based ...
Weighted tensor Golub–Kahan–Tikhonov-type methods applied to image processing using a t-product
Abstract
This paper discusses weighted tensor Golub–Kahan-type bidiagonalization processes using the t-product. This product was introduced in M.E. Kilmer and C.D. Martin (2011). A few steps of a bidiagonalization process with a weighted least ...
Fractional Tikhonov regularization for linear discrete ill-posed problems
Abstract
Tikhonov regularization is one of the most popular methods for solving linear systems of equations or linear least-squares problems with a severely ill-conditioned matrix A. This method replaces the given problem by a penalized least-squares ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Scientific Computing

Journal of Scientific Computing Volume 90, Issue 1

Jan 2022

1910 pages

ISSN:0885-7474

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.

Publisher

Plenum Press

United States

Publication History

Published: 01 January 2022

Accepted: 15 November 2021

Revision received: 20 April 2021

Received: 10 October 2020

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YZhao XDing MWang JJiang THuang T(2024)The Generalized Tensor Decomposition with Heterogeneous Tensor Product for Third-Order TensorsJournal of Scientific Computing10.1007/s10915-024-02637-8100:3Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1007/s10915-024-02637-8
Fan MLi J(2024)The Order-p Tensor Linear Complementarity Problem for Images DeblurringJournal of Scientific Computing10.1007/s10915-024-02502-899:2Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/s10915-024-02502-8
Lund KSchweitzer M(2023)The Fréchet derivative of the tensor t-functionCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-023-00527-360:3Online publication date: 16-Jun-2023
https://dl.acm.org/doi/10.1007/s10092-023-00527-3
Liao YLu T(2022)On Greedy Kaczmarz Method with Uniform Sampling for Consistent Tensor Linear Systems Based on T-ProductProceedings of the 6th International Conference on Advances in Image Processing10.1145/3577117.3577127(158-166)Online publication date: 18-Nov-2022
https://dl.acm.org/doi/10.1145/3577117.3577127

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents